John loves colorful things such as kaleidoscope. When he started to take advantage of Wolfram Alpha, a scientific computing tool, he fell in love with its current logo, a rhombic hexecontahedron, immediately.
Wolfram|Alpha Computational Intelligence
The rhombic hexecontahedron is a beautiful polyhedron which has 60 congruent rhombic faces. A rhombic hexecontahedron 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 to different extents. Also, a rhombic hexecontahedron can be constructed from a regular icosahedron, by appending three rhombuses to each of its faces such that each rhombus shares a vertex with it and every two rhombuses share an edge.
John wants to make some origami of rhombic hexecontahedron. Before getting started from scratch, he was wondering in how many different ways he can make origami of at most n types of colored paper. He has thought for a while and finally determined to leave this problem for you. Furthermore, he added some restriction such that a way of origami is counted if the number of faces colored by the i-th type of paper is at least ci (i = 1, 2, ..., n). Of course, the answer might be so large, so you just need to tell him the answer modulo some integer p.
Two ways are considered as the same if and only if there exists a way of rotation that can transform one to another so that each corresponding face has the same color. Here is an example of origami after coloring.
Picture from Wolfram Mathworld
In addition, he thought you might need a plane expansion for better understanding, however, because the plane expansion of a rhombic hexecontahedron is quite unreadable, he left here a modified plane expansion of a regular dodecahedron to illustrate approximately. Hope this image will help you solve this problem.
The first line contains one integer T, indicating 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).
It is guaranteed that no more than 100 test cases satisfy n > 5.
For each test case, print the answer modulo p in one line.
## Input
The first line contains one integer T, indicating 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).It is guaranteed that no more than 100 test cases satisfy n > 5.
## Output
For each test case, print the answer modulo p in one line.
[samples]
**Definitions**
Let $ F = 60 $ be the number of faces of the rhombic hexecontahedron.
Let $ n \in \mathbb{Z}^+ $ be the number of available colors.
Let $ \mathbf{c} = (c_1, c_2, \dots, c_n) \in \mathbb{Z}_{\geq 0}^n $ be the minimum required number of faces for each color, where $ \sum_{i=1}^n c_i \leq F $.
Let $ p \in \mathbb{Z} $ be the modulus, with $ 1 \leq p < 2^{30} $.
Let $ G $ be the rotation group of the rhombic hexecontahedron (isomorphic to the icosahedral group $ A_5 $, of order 60).
**Constraints**
1. $ 1 \leq T \leq 1000 $
2. $ 1 \leq n \leq 60 $, $ 0 \leq c_i \leq 60 $ for all $ i \in \{1, \dots, n\} $
3. $ \sum_{i=1}^n c_i \leq 60 $
4. At most 100 test cases have $ n > 5 $
**Objective**
For each test case, compute the number of distinct colorings of the 60 faces using $ n $ colors, such that color $ i $ is used at least $ c_i $ times, up to rotational symmetry. That is, compute:
$$
\left| \left\{ f: \{1,\dots,60\} \to \{1,\dots,n\} \,\middle|\, |\{j : f(j) = i\}| \geq c_i \text{ for all } i \in \{1,\dots,n\} \right\} / G \right| \mod p
$$
using Burnside’s lemma:
$$
\frac{1}{|G|} \sum_{g \in G} \sum_{\substack{\mathbf{k} \in \mathbb{Z}_{\geq 0}^n \\ \sum k_i = 60 \\ k_i \geq c_i}} \left[ \prod_{i=1}^n \binom{\text{cyc}_g(i)}{k_i} \right]
$$
where $ \text{cyc}_g(i) $ is the number of cycles of length $ i $ in the cycle decomposition of $ g $ acting on the 60 faces, and the inner sum is over color counts $ \mathbf{k} = (k_1, \dots, k_n) $ satisfying the constraints.
Due to the structure of the rhombic hexecontahedron’s rotation group, only conjugacy classes of $ G \cong A_5 $ need be considered, with known cycle types on the 60 faces.