Array Repairing

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.

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

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.

example 1:
1

example 2:
2

example 1:
0 0 0

example 2:
0 0 0
0 249561089 748683266

2020 Multi-University Training Contest 5