30513번 - 하이퍼 삼각형 자르기

$M$차원 하이퍼 삼각형은 $(M+1)$개의 꼭짓점을 갖는 $M$차원 정다포체다. $M=2$일 때 정삼각형, $M=3$일 때 정사면체가 이에 해당한다.

한 변의 길이가 $N$인 $M$차원 하이퍼 삼각형 모양 블록이 주어진다. 이 블록을 모든 모서리가 $N$등분되도록 블록의 각 $(M-1)$차원 면에 평행하게 나누자. 그 후 나누어진 블록을 몇 개 골라 원래 위치에서 움직이거나 돌리지 않고 합쳐 $M$차원 하이퍼 삼각형 모양 블록을 만들 수 있다. 이때 원래의 블록은 속이 꽉 차 있으며, 새로 만든 블록 역시 속에 빈 공간이 있으면 안 된다. 이때 $M$차원 하이퍼 삼각형 블록을 만드는 방법의 수를 구하는 프로그램을 작성하시오.

차원의 수 $M$과 한 변의 길이 $N$이 공백으로 구분되어 주어진다. $(2\leq M,N\leq 100\, 000)$

첫째 줄에 $M$차원 하이퍼 삼각형 블록을 만드는 방법의 수를 출력한다. 단, 수가 매우 커질 수 있으므로 $10^{9}+7$로 나눈 나머지를 출력한다. 이때 $10^{9}+7$은 소수다.

이 문제에서, $M$차원 유클리드 공간 안의 어떤 두 $(M-1)$차원 $a, b$에 대해 도형 $a$를 포함하는 무한 $(M-1)$차원 공간 $A$와 $b$를 포함하는 무한 $(M-1)$차원 공간 $B$를 설정했을 때 $A$에 속한 모든 점에 대해 그 점의 $B$로의 정사영까지의 거리가 항상 같고 그 값이 $0$이 아니라면 두 도형 $a, b$를 서로 평행하다고 정의한다.