배열의 흥미로운 세계

Gwen은 "배열의 흥미로운 세계"라는 제목의 박사 학위 논문을 거의 끝내려 한다. 그녀는 여러 종류의 배열을 연구하는데, 가장 좋아하는 것은 계수 배열이다. 계수 배열은 배열에서 가능한 각 값이 몇 번 나타나는지를 세는 배열이다. 형식적으로, A = [a0, a1, . . . , an−1]의 계수 배열 [c0, c1, c2, . . . , cn−1]은 A에 0이 c0개, 1이 c1개, 2가 c2개 있는 식으로 정의된다. 예를 들어 A = [4, 1, 2, 0, 2]라면 계수는 [1, 1, 2, 0, 1]이다. 계수 배열은 모든 0 ≤ i < n에 대해 ai가 정수이고 0 ≤ ai < n일 때만 정의된다.

Gwen의 논문 마지막 장은 mod-m 자기서술 배열에 관한 것이다. A = [a0, a1, . . . , an−1]의 계수 배열을 [c0, c1, . . . , cn−1]이라 하자. 양의 정수 m에 대해, 모든 0 ≤ i < n에서 ai ≡ ci (mod m)이면 A를 mod-m 자기서술 배열이라 한다. 즉, ai와 ci를 m으로 나눈 나머지가 같다. 예를 들어 A = [6, 6, 4, 6, 3, 5, 3]과 그 계수 배열 [0, 0, 0, 2, 1, 1, 3]을 보자. 둘은 mod 2에서 같으므로(둘 다 [0, 0, 0, 0, 1, 1, 1]이 된다), A는 mod-2 자기서술 배열이다.

Gwen이 논문을 제출하기 전에 남은 일은 여러 n과 m에 대해 mod-m 자기서술 배열의 개수를 계산하는 것뿐이다. 이 개수를 구하는 것을 도와주자.

입력은 배열의 길이 n (1 ≤ n ≤ 12)과 나머지 연산의 법 m (2 ≤ m ≤ 109)을 포함하는 한 줄로 이루어진다.

길이 n인 mod-m 자기서술 배열의 개수를 출력한다.