如果一个简单图的每个连通分量最多包含一个环，我们称该图为“好图”。

你的任务是计算所有具有 $n$ 个带标号顶点的“好图”中，属于某个环的边的总数。

为了避免计算巨大的整数，请输出该总数对 $p$ 取模的结果。

输入格式

输入包含多组测试数据。第一行包含两个整数 $T$ 和 $p$ ($1 \le T \le 3000$, $1 \le p \le 2^{30}$)，分别表示测试数据的组数和模数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 3000$)。

输出格式

对于每组测试数据，输出具有 $n$ 个带标号顶点的“好图”中，所有属于某个环的边的总数，对 $p$ 取模的结果，每组结果占一行。

样例

输入 1

7 998244353
1
2
3
4
5
6
7

输出 1

0
0
3
60
1050
19380
393750

说明

对于四个带标号顶点的“好图”，存在三种至少包含一个环的类型：

这些类型的图的数量分别为 3、12 和 4。因此，所需边的总数为 $3 \times 4 + 12 \times 3 + 4 \times 3 = 60$。