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)) mod 998244353.
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.