John 喜爱万花筒之类的色彩斑斓的事物。当他开始使用科学计算工具 Wolfram Alpha 时，他立刻爱上了它当前的标志——菱形六十面体。

Wolfram|Alpha 计算智能™

菱形六十面体是一个美丽的几何体，拥有 60 个全等的菱形面。菱形六十面体可以通过正十二面体构造：取其顶点、面中心和棱中心，并将它们从体心向外或向内缩放不同的程度。此外，菱形六十面体也可以通过正二十面体构造：在它的每个面上附加三个菱形，使得每个菱形与该面共享一个顶点，且每两个菱形共享一条棱。

John 想要制作一些菱形六十面体的折纸。在从零开始之前，他想知道用至多 $n$ 种颜色的纸制作折纸有多少种不同的方法。他思考了一会儿，最终决定把这个问题留给你。此外，他增加了一些限制：如果第 $i$ 种颜色的纸所覆盖的面数至少为 $c_i$ ($i = 1, 2, \dots, n$)，则该折纸方案被计入。当然，答案可能非常大，所以你只需要告诉他答案对某个整数 $p$ 取模的结果。

当且仅当存在一种旋转方式可以将一种方案变换为另一种方案，且使得每个对应的面颜色相同时，这两种方案被视为相同。以下是着色后的折纸示例。

图片来自 Wolfram Mathworld

此外，他认为你可能需要一个平面展开图来更好地理解，但由于菱形六十面体的平面展开图非常难以辨认，他在这里留下了一个正十二面体的修改版平面展开图以作近似说明。希望这张图能帮助你解决这个问题。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。 接下来的行描述了所有测试用例。对于每个测试用例： 第一行包含两个空格分隔的整数 $n$ 和 $p$。 第二行包含 $n$ 个空格分隔的整数 $c_1, c_2, \dots, c_n$。 $1 \le T \le 1000, 1 \le n \le 60, 1 \le p < 2^{30}, 0 \le c_i \le 60$ ($i = 1, 2, \dots, n$)。 保证满足 $n > 5$ 的测试用例不超过 100 个。

输出格式

对于每个测试用例，在一行中输出答案对 $p$ 取模的结果。

样例

样例输入 1

5
2 1000000007
0 0
2 1000000007
1 0
2 1000000007
0 2
2 1000000007
1 1
5 1000000007
1 1 1 1 1

样例输出 1

544393230
544393229
544393228
544393228
905148476