We define the value of an unrooted tree T as , 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 (, 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 ().

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

5 1000000007
2
3
4
5
107

2
24
264
3240
736935633