Description

We define an undirected simple graph to be good as follows:

1. A single vertex is good.

2. A graph formed by taking several good graphs as connected components is good.

3. The complement of a good graph is good.

Given a positive integer $n$.

Find, modulo the prime $P$, the number of essentially different good graphs on $n$ vertices. (Here $P$ is a constant; see Input Format for details.)

Two good graphs are considered essentially different if and only if, no matter how you relabel one graph, it still cannot become exactly the same as the other graph.

Input Format

The input contains multiple test cases. The first line contains two integers $T, P$ separated by spaces, representing the number of test cases and the modulus. Then each test case is described as follows:

• One line with one integer $n$, meaning the number of vertices of the good graphs to be counted.

Output Format

For each test case, output one line:

• One integer, the number of good graphs on $n$ vertices modulo $P$.

2 233
3
4

4
10

Hint

Sample Explanation

Below are all good graphs with $3$ vertices:

Constraints

It is guaranteed that $T \leq 233$, $n \leq 23333$, $2^{29} < P < 2^{30}$, and $P$ is prime.

Hint

The time complexity of an algorithm that can pass this problem might be worse than you expect, or it might be better than you expect.

Copyright Information

From the 2018 Tsinghua University Programming Contest and Collegiate Invitational (THUPC2018). Thanks to Pony.ai for supporting this contest.

Resources such as editorials can be found at https://github.com/wangyurzee7/THUPC2018.

Translated by ChatGPT 5