我们定义一棵无根树 $T$ 的价值为 $\sum_{u \in V(T)} (d(u))^2$，其中 $V(T)$ 是 $T$ 的顶点集，$d(u)$ 是顶点 $u$ 的度数。我们定义一个森林的价值为其中所有树的价值之和。现在请你计算所有具有 $N$ 个带标号顶点的森林的价值之和。
为了避免大整数计算，请输出答案对质数 $M$ 取模的结果。
输入格式
输入包含多组测试数据。第一行包含两个整数 $T$ 和 $M$ ($1 \le T \le 5000, 1 \le M \le 2^{30}$，且 $M$ 为质数)，分别表示测试数据的组数和模数。
对于每组测试数据，仅包含一行一个整数 $N$ ($1 \le N \le 5000$)。
输出格式
对于每组测试数据，输出所有森林的价值之和对 $M$ 取模的结果，每组结果占一行。
样例
样例输入 1
5 1000000007 2 3 4 5 107
样例输出 1
2 24 264 3240 736935633