Camp room assignment

Time limit3sMemory limit1024 MB

Summary

For each n from 1 to m, count the length-2n sequences over m universities in which no university appears more than n times.

Level: Medium6 of 10
Topics: Combinatorics, Math
Solved: No attempts yet

Problem

In the JAG country, there are a total of $m$ universities, and we plan to invite $2n$ students to a training camp. Each student is affiliated with one of the $m$ universities. During the camp, the students will be accommodated in $n$ twin rooms, so each room is assigned exactly two students.

A room assignment is good if and only if the two students sharing each room come from different universities.

We want to know how often a good room assignment is feasible. There are $m^{2n}$ possible sequences of university affiliations. Find how many of them admit a good room assignment.

We do not yet know how many rooms we can provide. Therefore, for each $n = 1, 2, \dots, m$ , find how many sequences of university affiliations admit a good room assignment.

Since the answer may be huge, print the answers modulo $998\,244\,353$ .

Input

The input is a single line containing an integer $m$ between $1$ and $200\,000$ , inclusive.

Output

Output $m$ lines. On the $i$ -th line, output the answer for $n = i$ .

Examples3

Example 1
Input
```
3
```
Expected output
```
6
54
510
```
Example 2
Input
```
5
```
Expected output
```
20
540
14300
370300
9454620
```

Example 3

Input

Expected output