Sum of Cosecant Power Series Modulo 998244353

Given three positive integers n, m and s satisfying gcd(n,s)=1, you are to compute the following sum modulo 998244353:

$$S = \sum_{k=1}^{n-1} \sin^{-2m}\Bigl(\frac{k\,s}{n}\pi\Bigr). $$

It can be proved that the answer is always a rational number. When the answer is an irreducible fraction \(\frac{a}{b}\), you should output the unique integer \(x\) with \(0\le x<998244353\) satisfying \(x\cdot b\equiv a\pmod{998244353}\). For details on how to take the modulo of a rational number, please refer to problem P2613.

Note: Since s is relatively prime to n, the set \(\{ks\mod n:1\le k\le n-1\}\) is just a permutation of \(\{1,2,\ldots,n-1\}\). Therefore the answer is independent of s and is equivalent to computing

$$S = \sum_{k=1}^{n-1} \csc^{2m}\Bigl(\frac{k\pi}{n}\Bigr). $$

Constraints: For the purpose of this problem, you may assume m is small (for example, m\le 3) so that closed‐form formulas exist. In particular, the following formulas hold:

• When m = 1: \(S = \frac{n^2-1}{3}\).
• When m = 2: \(S = \frac{(n^2-1)(n^2+11)}{45}\).
• When m = 3: \(S = \frac{(n^2-1)(2n^4+23n^2+191)}{945}\).

For any other value of m not covered above you may output 0.

inputFormat

The input consists of a single line containing three integers n, m and s separated by spaces.

outputFormat

Print the answer, that is, the unique integer x in the range \(0\le x<998244353\) such that if the answer is the reduced fraction \(\frac{a}{b}\), then \(x\cdot b\equiv a\pmod{998244353}\).

sample

4 1 1

5