Kaleidoscope
Time limit2sMemory limit512 MB
Count colorings of the 60 faces of a rhombic hexecontahedron with n colors, each color i used at least c_i times, where colorings are identified under the rotational symmetry group, modulo p.
- Level
Hard9 of 10
- Topics
- Combinatorics, Math, Dynamic programming, BFS
- Solved
- No attempts yet
Problem
John loves colorful things such as kaleidoscopes. When he started using Wolfram Alpha, a scientific computing tool, he fell in love with its logo at the time, a rhombic hexecontahedron, immediately.
Wolfram|Alpha Computational IntelligenceTM
The rhombic hexecontahedron is a beautiful polyhedron with 60 congruent rhombic faces. It can be constructed from a regular dodecahedron by taking its vertices, its face centers, and its edge centers and scaling them in or out from the body center by different amounts. It can also be constructed from a regular icosahedron by appending three rhombuses to each of its faces, where each rhombus shares a vertex with the icosahedron and every two rhombuses share an edge.
John wants to make an origami model of a rhombic hexecontahedron. Before starting from scratch, he wondered how many different ways he can make origami from at most n types of colored paper. After thinking for a while, he decided to leave this problem to you. He also added a restriction: a way counts only if the number of faces colored with the i-th type of paper is at least ci (i = 1, 2, . . . , n). The answer can of course be very large, so you only need to report it modulo some integer p.
Two ways are considered the same if and only if there is a rotation that transforms one into the other so that every pair of corresponding faces has the same color. Here is an example of origami after coloring.
Picture from Wolfram Mathworld
He also thought you might need a plane expansion for better understanding. However, since the plane expansion of a rhombic hexecontahedron is quite unreadable, he left a modified plane expansion of a regular dodecahedron to illustrate approximately. We hope this image helps you solve the problem.
Input
The first line contains one integer T, the number of test cases.
The following lines describe all the test cases. For each test case:
The first line contains two space-separated integers n and p.
The second line contains n space-separated integers c1, c2, . . . , cn.
1 ≤ T ≤ 1000, 1 ≤ n ≤ 60, 1 ≤ p < 230, 0 ≤ ci ≤ 60 (i = 1, 2, . . . , n).
No more than 100 test cases satisfy n > 5.
Output
For each test case, print the answer modulo p in one line.