中文
日本語
English
| P4864化学题 | ||
|
Description
计算化学式为 \(\rm C_n H_{2n+2}\) 的烷烃的同分异构体个数。
多组数据，答案对 $998244353$ 取模。
Input Format
第一行一个整数 \(T\)，表示数据组数。
接下来 \(T\) 行，每行一个整数 \(n\)，表示询问化学式为 \(\rm C_n H_{2n+2}\) 的烷烃的同分异构体个数。
Output Format
共输出 \(T\) 行，每行一个整数，表示答案。
Sample Input
5
3
4
5
233
666
Sample Output
1
2
3
134793965
35803200
Hint
| 测试点编号 | \(T\) | \(n\) | 分值 |
|---|---|---|---|
| 1 | \(=1\) | \(\leq 8\) | $5$ |
| 2 | \(=1\) | \(\leq 200\) | $5$ |
| 3 | \(=1\) | \(\leq 200\) | $5$ |
| 4 | \(=1\) | \(\leq 2000\) | $5$ |
| 5 | \(=1\) | \(\leq 2000\) | $5$ |
| 6 | \(=1\) | \(\leq 2000\) | $5$ |
| 7 | \(=1\) | \(= 66666\) | $5$ |
| 8 | \(=1\) | \(\leq 10^5\) | $5$ |
| 9 | \(=1\) | \(\leq 10^5\) | $5$ |
| 10 | \(=1\) | \(\leq 10^5\) | $5$ |
| 11 | \(=1\) | \(\leq 10^5\) | $5$ |
| 12 | \(=1\) | \(\leq 10^5\) | $5$ |
| 13 | \(=10^5\) | \(\leq 10^5\) | $40$ |
提示：如果你不知道什么是烷烃，那么你可以认为这个问题等价于求 \(n\) 个点的无标号无根树并满足每个点的度数 \(\leq 4\) 的树的个数。