P9374 "DROI" Round 2 Single Graph

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

We say that two [simple directed graphs](https://www.luogu.com.cn/paste/4oz6fep2) $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.

**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 $T$ lines. The $i$-th line should contain the answer for the $i$-th test case modulo $mod$.

#### 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: ------------ [](https://www.luogu.com.cn/paste/0tbbkesd) 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