하이퍼 삼각형 자르기

$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$는 서로 평행하다고 정의한다.