Array Repairing

Problem Description

Given an integer $n$, a sequence $a[1..n]$ is randomly generated with equal probability, namely, $a_i \in [1,n]$, $\forall i \in [1,n]$. Note that it may be not a permutation of $1..n$. To turn it into $a_i=i,\forall i \in [1,n]$, you can perform any of the following two operations for any times: 1.Choose $i,j \in [1,n],i\not = j$, swap $a_i,a_j$ costing $1$. 2.Choose $i,v \in [1,n]$, set $a_i = v$ costing $k$. For example, if you perform operations of the first kind for $5$ times and perform operations of the second kind for $4$ times, then it will cost you $4 \times k + 5$. Denote $cost_k(a)$ as the minimum total cost for the sequence $a$ with the parameter $k$. For each $k \in [0,2]$, print the mathematical expectation $E(cost_k(a))$ $mod$ $998244353$. Now, you need to answer the above question for each $n \in [1,N]$. That is to say, you should print $3 \times N$ values in total.

Input

One line contains only one integer $N$, $N \in [1,\ 5 \times 10^5]$.

Output

You should output $N$ lines with each containing $3$ values $E(cost_k(a))$ $mod$ $998244353$, $\forall k \in [0,2]$ separated by two spaces.

Sample Input

example 1:
1
example 2:
2

Sample Output

example 1:
0 0 0
example 2:
0 0 0
0 249561089 748683266

Source

2020 Multi-University Training Contest 5