{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eJohn 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.\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/400a53661eaaaca50b776f071d6e456f?v\u003d1715728712\"\u003e\u003cbr\u003eWolfram|Alpha Computational Intelligence$^{\\mathrm{TM}}$\u003c/center\u003e\u003cbr\u003e\u003cbr\u003eThe 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.\u003cbr\u003e\u003cbr\u003eJohn 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 $c_i$ $(i \u003d 1, 2, \\cdots, n)$. Of course, the answer might be so large, so you just need to tell him the answer modulo some integer $p$.\u003cbr\u003e\u003cbr\u003eTwo 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.\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/74baa3fdba6be1f499d21f3461d1047d?v\u003d1715728712\"\u003e\u003cbr\u003ePicture from Wolfram Mathworld\u003c/center\u003e \u003cbr\u003e\u003cbr\u003eIn 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.\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/be7eef7faf4821a9758fa353c219050c?v\u003d1715728712\"\u003e\u003c/center\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains one integer $T$, indicating the number of test cases.\u003cbr\u003eThe following lines describe all the test cases. For each test case:\u003cbr\u003eThe first line contains two space-separated integers $n$ and $p$.\u003cbr\u003eThe second line contains $n$ space-separated integers $c_1, c_2, \\cdots, c_n$.\u003cbr\u003e$1 \\leq T \\leq 1000$, $1 \\leq n \\leq 60$, $1 \\leq p \u0026lt; 2^{30}\u003cbr\u003e$, $0 \\leq c_i \\leq 60$ $(i \u003d 1, 2, \\cdots, n)$.\u003cbr\u003eIt is guaranteed that no more than $100$ test cases satisfy $n \u0026gt; 5$.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, print the answer modulo $p$ in one line.\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\n2 1000000007\r\n0 0\r\n2 1000000007\r\n1 0\r\n2 1000000007\r\n0 2\r\n2 1000000007\r\n1 1\r\n5 1000000007\r\n1 1 1 1 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e544393230\r\n544393229\r\n544393228\r\n544393228\r\n905148476\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}