만화경
시간 제한2초메모리 제한512 MB
마름모 육십면체의 60개 면을 n가지 색으로 칠하되 각 색 i를 최소 c_i번 사용하고, 회전 대칭으로 같은 색칠은 동일하게 볼 때 경우의 수를 p로 나눈 나머지를 구한다.
문제
John은 만화경처럼 알록달록한 것을 좋아한다. 과학 계산 도구인 Wolfram Alpha를 쓰기 시작했을 때, 그는 그 도구의 당시 로고인 마름모육십면체에 곧바로 반했다.
Wolfram|Alpha Computational IntelligenceTM
마름모육십면체는 합동인 마름모 60개를 면으로 가진 아름다운 다면체이다. 마름모육십면체는 정십이면체에서 꼭짓점, 면의 중심, 모서리의 중심을 몸통 중심에서 서로 다른 비율로 확대하거나 축소해 만들 수 있다. 또 정이십면체에서 각 면에 마름모 3개를 붙여 만들 수도 있는데, 각 마름모는 정이십면체와 꼭짓점 하나를 공유하고 두 마름모는 모서리를 공유한다.
John은 마름모육십면체 종이접기를 만들려고 한다. 처음부터 만들기 전에, 그는 최대 n종류의 색종이로 종이접기를 만드는 서로 다른 방법이 몇 가지인지 궁금해졌다. 한참 고민한 끝에 이 문제를 당신에게 맡기기로 했다. 게다가 그는 i번째 종류의 종이로 색칠된 면의 수가 ci 이상일 때만 그 방법을 인정한다는 제한을 추가했다 (i = 1, 2, . . . , n). 물론 답이 매우 클 수 있으므로 어떤 정수 p로 나눈 나머지를 구하면 된다.
두 방법은, 한쪽을 회전시켜 다른 쪽으로 변환했을 때 대응하는 모든 면의 색이 같아지는 회전이 존재할 때에만 같은 방법으로 본다. 다음은 색칠을 마친 종이접기의 예시이다.
Picture from Wolfram Mathworld
또한 그는 이해를 돕기 위해 평면 전개도가 필요할 수 있다고 생각했지만, 마름모육십면체의 평면 전개도는 알아보기 힘들어서 대략적인 설명을 위해 정십이면체의 변형된 평면 전개도를 대신 남겼다. 이 그림이 문제를 푸는 데 도움이 되기를 바란다.
입력
첫째 줄에 테스트 케이스의 수를 나타내는 정수 T가 주어진다.
다음 줄부터 모든 테스트 케이스가 주어진다. 각 테스트 케이스는 다음과 같다.
첫째 줄에 공백으로 구분된 두 정수 n과 p가 주어진다.
둘째 줄에 공백으로 구분된 n개의 정수 c1, c2, . . . , cn이 주어진다.
1 ≤ T ≤ 1000, 1 ≤ n ≤ 60, 1 ≤ p < 230, 0 ≤ ci ≤ 60 (i = 1, 2, . . . , n).
n > 5인 테스트 케이스는 100개를 넘지 않는다.
출력
각 테스트 케이스마다 답을 p로 나눈 나머지를 한 줄에 출력한다.