#6569. 仙人掌计数

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cx233666

题目描述

这是 JOHNKRAM 课件里的题,但由于他好像并没有造数据,所以我来传一下。

这是一道 easy 题。

鸭鸭脖 (yybyyb) 想知道 n 个节点仙人掌一共有多少个,大鸽鸽觉得这是 sb 题懒得做,于是把这道题丢给了你,你能帮助鸭鸭脖吗?

无重边、自环,有标号。

输入格式

输入一行 Q 。表示有 Q 组询问。

接下来 Q 行,每行一个 n

输出格式

输出 Q 行表示答案模 998244353 的结果。

样例

输入
7
3
5
76594
114337
128586
63931
95399
输出
4
362
967806766
664576273
918824003
750818040
549838174

数据范围与提示

n < 131072,Q \le 50000