Given an integer n, a sequence a[1..n] is randomly generated with equal probability, namely, ai∈[1,n], ∀i∈[1,n]. Note that it may be not a permutation of 1..n.
To turn it into ai=i,∀i∈[1,n], you can perform any of the following two operations for any times:
1.Choose i,j∈[1,n],i≠j, swap ai,aj costing 1.
2.Choose i,v∈[1,n], set ai=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×k+5.
Denote costk(a) as the minimum total cost for the sequence a with the parameter k. For each k∈[0,2], print the mathematical expectation E(costk(a))mod998244353.
Now, you need to answer the above question for each n∈[1,N]. That is to say, you should print 3×N values in total.
输入格式
One line contains only one integer N, N∈[1, 5×105].
输出格式
You should output N lines with each containing 3 values E(costk(a))mod998244353, ∀k∈[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