#1638. 「雅礼集训 2018 Day8」C

    ID: 1638 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>DFT(含 NTT)及FFT雅礼集训生成函数 / 母函数分治2018

「雅礼集训 2018 Day8」C

题目描述

计算化学式为 CnH2n+2{\rm C}_n{\rm H}_{2n+2} 的烷烃的同分异构体个数。

多组数据,答案对 998244353998244353 取模。

提示:如果你不知道什么是烷烃,那么你可以认为这个问题等价于求 nn 个点的无标号无根树并满足每个点的度数 4\leq 4 的树的个数。

输入格式

第一行一个整数 TT,表示数据组数。

接下来 TT 行,每行一个整数 nn,表示询问化学式为 CnH2n+2{\rm C}_n{\rm H}_{2n + 2} 的烷烃的同分异构体个数。

输出格式

共输出 TT 行,每行一个整数,表示答案。

样例

5
3
4
5
233
666
1
2
3
134793965
35803200

数据范围与提示

测试点编号 TT nn 分值
11 =1=1 8\leq 8 55
22 200\leq 200 55
33 55
44 2000\leq 2000 55
55 55
66 55
77 =66666= 66666 55
88 105\leq 10^5 55
99 55
1010 55
1111 55
1212 55
1313 =105=10^5 4040