3843: Desert
内存限制：256 MB
时间限制：15.000 S
评测方式：文本比较
命题人：
提交：5
解决：2
题目描述
Tom and Jerry got lost in a desert. But they are not bored or afraid at all, because they found a truly interesting thing to do: researching the varied kinds of kakti in the desert!
After careful observations, they found that a kaktus can be seen as a graph consisting of several nodes. To be precise, an n-node kaktus is an undirected connected graph that has only 1node as the root, in which every edge belongs to exactly one simple cycle and all nodes are unlabelled. You can refer to sample case for a better understanding.
Finding something new is always exciting, but it brings them new doubts.
"How many different kinds of n-node kakti are there?" wondered Tom.
"Your problem is simpler than mine. I am wondering how many different kinds of 1,2,3,..,n-node kakti there are." said Jerry.
After careful observations, they found that a kaktus can be seen as a graph consisting of several nodes. To be precise, an n-node kaktus is an undirected connected graph that has only 1node as the root, in which every edge belongs to exactly one simple cycle and all nodes are unlabelled. You can refer to sample case for a better understanding.
Finding something new is always exciting, but it brings them new doubts.
"How many different kinds of n-node kakti are there?" wondered Tom.
"Your problem is simpler than mine. I am wondering how many different kinds of 1,2,3,..,n-node kakti there are." said Jerry.
输入
One line containing a number n (1≤n≤10^5).
输出
nlines, each line containing a number, the number of n-node kakti.
As these numbers can be very large, output them modulo 998244353.
As these numbers can be very large, output them modulo 998244353.
样例输入 复制
4
样例输出 复制
1
1
3
8