408134: GYM102993 I Valuable Forests

We define the value of an unrooted tree $$$T$$$ as $$$\sum_{u \in V(T)} (d(u))^2$$$, where $$$V(T)$$$ is the set of all vertices of $$$T$$$, and $$$d(u)$$$ is the degree of the vertex $$$u$$$. We define the value of a forest as the sum of the value of all trees from it. Now we want you to answer the sum of the value of all forests with $$$N$$$ labeled vertices.

In order to avoid calculations of huge integers, report answer modulo a prime $$$M$$$ instead.

There are multiple test cases. The first line of the input contains two integers $$$T$$$ and $$$M$$$ ($$$ 1 \le T \le 5000, 1 \le M \le 2^{30}$$$, and $$$M$$$ is a prime), indicating the number of test cases and the modulus.

For each test case, the only line contains an only integer $$$N$$$ ($$$1 \le N \le 5000$$$).

For each test case, output the sum of answer modulo $$$M$$$ in one line.

5 1000000007
2
3
4
5
107

2
24
264
3240
736935633