Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

M. Random Spanning Tree
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

We say that the diameter of a tree is any longest simple path in that tree, and we measure the length of a path by the number of edges it contains.

You are given a positive integer $$$n$$$. Consider the undirected complete graph on vertices $$$\{1,2,\ldots,n\}$$$. A spanning tree $$$T$$$ is chosen uniformly at random among all spanning trees satisfying that the simple path between vertices $$$1$$$ and $$$n$$$ is a diameter of $$$T$$$. Equivalently, if $$$d(u,v)$$$ denotes the distance (number of edges) between $$$u$$$ and $$$v$$$ in $$$T$$$, then $$$$$$ d(1,n) \;=\; \max_{1 \le x \lt y \le n} d(x,y). $$$$$$

Let $$$$$$ D \;=\; d(1,n) $$$$$$ in the chosen tree. We have $$$$$$ \mathbb{E}[D] \;=\;\frac{P}{Q}, $$$$$$ a rational number, where $$$\mathbb{E}[D]$$$ denotes the expected (average) value of the random variable $$$D$$$ taken over all valid spanning trees $$$T$$$ chosen under the given condition.

You are also given an integer $$$m$$$. Since $$$\mathbb{E}[D]$$$ is a rational number $$$\frac{P}{Q}$$$ (with $$$Q$$$ coprime to $$$m$$$), output the value of $$$P \cdot Q^{-1} \bmod m$$$, where $$$Q^{-1}$$$ denotes the modular inverse of $$$Q$$$ modulo $$$m$$$.

Input

The first line contains two integers:

  • $$$t$$$ ($$$1 \le t \le 500$$$) — the number of testcases.
  • $$$m$$$ ($$$10^8 \le m \le 10^9$$$, $$$m$$$ is prime).
Each of the next $$$t$$$ lines contains a single integer $$${n \space\space (1 \le n \le 500)}$$$ — denoting the number of nodes in the graph for that testcase.
Output

For each testcase, output in the answer to the problem modulo $$$m$$$ in a separate line.

Example
Input
8 711787309
1
2
3
4
5
6
7
8
Output
0
1
2
355893657
305051707
211612447
511987367
529573609