Camp room assignment

시간 제한3초메모리 제한1024 MB

요약

m개의 대학이 있을 때, 2n명의 소속 대학을 나열한 수열 중에서 같은 방에 배정된 두 학생이 서로 다른 대학이 되도록 n개의 방에 짝지을 수 있는 수열의 개수를 n=1부터 m까지 각각 구한다.

난이도: 보통10점 중 7점
유형: 조합론, 동적 계획법, 수학, 정렬
정답자: 아직 제출이 없습니다

문제

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 training camp, the students will be accommodated in $n$ twin rooms, meaning that each room will be assigned to exactly two students.

To promote diverse interactions among the students, our goal is to achieve a "good room assignment". A room assignment is considered good if and only if the students sharing the same room come from different universities.

Here, we are wondering how often a good room assignment is feasible. There are $m^{2n}$ possible sequences of universities to which each student belongs, and please find for how many of them there is a good room assignment.

Actually, we don't yet know how many rooms we can provide. Therefore, for each of $n = 1, 2, \dots , m$ , please find for how many of the sequences of universities there is a good room assignment.

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

입력

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

출력

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

예제3

예제 1
입력
```
3
```
예상 출력
```
6
54
510
```
예제 2
입력
```
5
```
예상 출력
```
20
540
14300
370300
9454620
```

예제 3

입력

예상 출력