하이퍼 삼각형 자르기
시간 제한1초메모리 제한1024 MB
한 변의 길이가 N인 M차원 하이퍼 삼각형을 N등분한 단위 조각을 골라 빈틈 없이 같은 모양으로 다시 합치는 방법의 수를 10^9+7로 나눈 나머지로 구한다.
문제
차원 하이퍼 삼각형은 개의 꼭짓점을 갖는 차원 정다포체다. 일 때 정삼각형, 일 때 정사면체가 이에 해당한다.
한 변의 길이가 인 차원 하이퍼 삼각형 모양 블록이 주어진다. 이 블록을 모든 모서리가 등분되도록 블록의 각 차원 면에 평행하게 나누자. 그 후 나누어진 블록을 몇 개 골라 원래 위치에서 움직이거나 돌리지 않고 합쳐 차원 하이퍼 삼각형 모양 블록을 만들 수 있다. 이때 원래의 블록은 속이 꽉 차 있으며, 새로 만든 블록 역시 속에 빈 공간이 있으면 안 된다. 이때 차원 하이퍼 삼각형 블록을 만드는 방법의 수를 구하는 프로그램을 작성하시오.
입력
차원의 수 과 한 변의 길이 이 공백으로 구분되어 주어진다.
출력
첫째 줄에 차원 하이퍼 삼각형 블록을 만드는 방법의 수를 출력한다. 단, 수가 매우 커질 수 있으므로 로 나눈 나머지를 출력한다. 이때 은 소수다.
힌트
이 문제에서, 차원 유클리드 공간 안의 어떤 두 차원 에 대해 도형 를 포함하는 무한 차원 공간 와 를 포함하는 무한 차원 공간 를 설정했을 때 에 속한 모든 점에 대해 그 점의 로의 정사영까지의 거리가 항상 같고 그 값이 이 아니라면 두 도형 를 서로 평행하다고 정의한다.