Roundgod has a permutation of length nnn. She plans to sort the permutation in ascending order with an algorithm depends on luck. At any time, Roundgod could spend∣S∣|S|∣S∣ money to choose a subsetS
Roundgod has a permutation of length nnn. She plans to sort the permutation in ascending order with an algorithm depends on luck. At any time, Roundgod could spend ∣S∣|S|∣S∣ money to choose a subset SSS of indices and then uniformly shuffle the values in corresponding positions, where ∣S∣|S|∣S∣ means the size of SSS. She wants to know the expected value of minimum cost to sort the permutation under the optimal decision. Only one permutation can't show Roundgod's luck clearly, so lzr gives Roundgod mmm permutations. It can be proved that the expected values can always be written in reduced fraction PQfrac P QQP, where QQQ is not a multiple of 998244353998244353998244353. Please tell Roundgod the answer for each permutation by P⋅Q−1(mod 998244353)P cdot Q ^{-1} (textrm{mod} 998244353)P⋅Q−1(mod 998244353) , where Q−1Q^{-1}Q−1 is the multiplicative inverse modulo 998244353998244353998244353.