测试数据来自 system/1564

背景

这是最后一题了。

描述

给定一个n，要求不定方程\(n^2=x^2+y^2\)的整数解个数。zgx做了这题后，认为太简单，于是就扩大了数据范围。为了能创造出足够大的数，我们令:

\(n=a_1^{a_2^{a_3^{\cdots ^{a_k}}}}\)，

我们通过输入数列\(\{a_k\}\)这k个数来计算n。

例如，\(k=3\)，\(a_1=5\)，\(a_2=2\)，\(a_3=3\)，那么\(n=5^{2^3}=390625\)，现在还是要求\(n^2=x^2+y^2\)的整数解个数，但由于整数解个数实在太多了！我们只要输出答案mod p的值即可。

格式

输入格式

第一行，两个数k，p。(\(k, p\le 10000\))
第二行，k个数。 每个数\(\le 10000\)。所有数都是质数，且都大于p。

输出格式

一行，\(n^2=x^2+y^2\)的整数解个数mod p的值。

样例1

样例输入1

2 3
5 7

样例输出1

0

样例2

样例输入2

1 5
7

样例输出2

4

提示

样例2说明：
4个解分别为：①x=7,y=0 ②x=-7,y=0 ③x=0,y=7 ④x=0,y=-7

数据规模：
对于20%的数据计算出来的\(n\le 10^8\)
对于100%的数据\(k,p\le 10000\)，每个数\(a_i\le 10000\)

Hint:

\(n=a_1^{a_2^{a_3^{\cdots ^{a_k}}}}\)，是从后向前算的，也就是n=\(a_1\)^(\(a_2\)^(\(a_3\)^(\(\cdots\)^\(a_k\))))。