Inversion Sum After Prime Sorting

Consider a permutation of the numbers from 1 to n. We define a prime sort on a sequence as follows: Collect all positions whose indices are prime numbers (the indices are 1-indexed) and sort the numbers in these positions in ascending order, while leaving the other positions unchanged.

For example, given the sequence:

the prime indices within \(\{1,2,3,\dots,8\}\) are \(2,3,5,7\). Extracting the numbers at these positions we obtain \(7,6,4,2\), which when sorted in ascending order give \(2,4,6,7\). Placing these sorted numbers back into their original prime-index positions, the transformed sequence is:

For each permutation \(P\) of \(\{1,2,\dots,n\}\), define \(Q\) as the permutation obtained by performing prime sort on \(P\). Let an inversion in a sequence \(Q\) be a pair \((i,j)\) with \(iQ[j]\). Your task is to compute the sum of the number of inversions of \(Q\) over all \(n!\) permutations of \(\{1,2,\dots,n\}\;\) and output the answer modulo \(998244353\).

Hint: Note that only the positions corresponding to prime indices are affected by the sorting process. For a given pair of indices \((i,j)\), consider whether each index is prime or not in order to calculate the probability that \(Q[i]>Q[j]\) in the transformed permutation. Use linearity of expectation and symmetry to derive a formula that involves computing the factorial \(n!\), binomial coefficients on the count of non–prime indices, and summations over the prime indices. Remember to perform modular inversions when dividing modulo \(998244353\).

inputFormat

The input consists of a single integer \(n\) \((1 \le n \le 10^5)\), which denotes the size of the permutation \(\{1,2,\dots,n\}\).

outputFormat

Output a single integer: the sum of inversion counts after applying prime sort on all permutations of \(\{1,2,\dots,n\}\) modulo \(998244353\).

sample

1

0