Background

Rather than writing a weak background, it is better to make a higher-quality problem.

Problem Description

We say that two simple directed graphs $G, H$ are essentially the same if and only if:

• For any pair of vertices $(u, v)$, if in graph $G$ one can reach $v$ starting from $u$, then in graph $H$ one can also reach $v$ starting from $u$. Conversely, if in graph $H$ one can reach $v$ starting from $u$, then in graph $G$ one can also reach $v$ starting from $u$.

If for a simple directed graph $G$, there does not exist any other simple directed graph $H$ that is essentially the same as it, then we call graph $G$ a single graph.

There are $T$ queries. In each query, a positive integer $n$ is given. Please output the number of labeled single graphs with $n$ vertices.

Input Format

This problem uses multiple test cases.

The first line contains two integers $T, mod$, representing the number of test cases and the modulus.

The next $T$ lines each contain one integer, representing $n$ for that test case.

Output Format

Output $T$ lines. The $i$-th line should contain the answer for the $i$-th test case modulo $mod$.

5 998244353
1
3
5
12
888

1
16
986
328006912
535268381

Hint

Constraints

"This problem uses bundled testdata."

• $\operatorname{Subtask} 1(30\%)$: $T = 1$, $n \leq 5$.

• $\operatorname{Subtask} 2(50\%)$: $T \leq 10$.

• $\operatorname{Subtask} 3(20\%)$: no special constraints.

For $100\%$ of the testdata: $1 \leq T, n \leq 1000$, $1 \leq mod \leq 10^9$.

Notes

Some examples are given here to help you understand what a single graph means:

This is a single graph. It can be proven that there is no other graph that is essentially the same as it.

This is not a single graph, because we can add the edge $(5, 2)$ to construct a graph that is essentially the same as it.

This is not a single graph, because we can delete the edge $(1, 3)$ to construct a graph that is essentially the same as it.

Translated by ChatGPT 5