Edges Counting

A simple graph is called good if each of its connected components contains at most one cycle.

For all good graphs with $n$ labeled vertices, count the number of edges that belong to a cycle.

To avoid computing huge integers, report the sum of these edge counts modulo $p$.

The input contains multiple test cases. The first line contains two integers $T$ and $p$ ($1 \le T \le 3000$, $1 \le p \le 2^{30}$), where $T$ is the number of test cases and $p$ is the modulus. Each test case is as follows.

The first line contains a single integer $n$ ($1 \leq n \leq 3000$).

For each test case, output the sum of the edge counts modulo $p$ on one line.

Among the good graphs with four labeled vertices, three types contain a cycle.

The numbers of these graphs are $3$, $12$, and $4$. Therefore the sum of the edge counts is $3 \times 4 + 12 \times 3 + 4 \times 3 = 60$.