Background

Please note: the background of the problem may not be related to the problem.

One day, Xiao Zhou was studying a very fast sieve. He was very unhappy with the notation of the Zhouge sieve’s complexity $O\left(\frac{n^{3/4}}{\log n}\right)$. Why does an algorithm that does not need to use a bitset have a division in its complexity?

Xiao Zhou suddenly came up with a good idea. Since the order of the logarithm function is lower than that of power functions, let $\epsilon$ denote an infinitesimal, and then we can make $\log n = O(n^\epsilon)$! Thus, Xiao Zhou excitedly thought, we can directly let $\log n$ correspond to some specific infinitesimal $\epsilon _0$, and then the complexity of the Zhouge sieve can be written as $O(n^{3/4 - \epsilon_0})$!

So pretty!

At this moment, a classmate named whk came over.

“Why do you people in informatics still need the vacuum permittivity?”

Problem Description

Given positive integers $n, m, s$, with $\gcd(n, s) = 1$. Compute

$$\sum_{k = 1}^{n-1} \sin^{-2m} \left(\frac{ks}{n}\pi\right)$$

modulo $998244353$.

It can be proven that the answer must be a rational number. For how to take a rational number modulo, please refer to P2613 Rational Number Modulo.

Input Format

A single line with three positive integers $n, m, s$.

Output Format

A single line with one integer, representing the answer modulo $998244353$.

4 3 1

17

11451 19198 11451419198

473735219

Hint

$\textbf{Subtask}$	$n\le$	$m\le$	$s\le$	Score
$1$	$3$		$1$	$5$
$2$	$10^5$	$1$		$10$
$3$		$50$	$10^{18}$	$20$
$4$	$50$	$10^5$
$5$	$10^5$	$10^{18}$		$45$

For all testdata, it is guaranteed that $1\le n \le 10^5$ and $1\le m,s \le 10^{18}$.

Hint: contestants should pay attention to the impact of constant factors in the complexity on the program’s running efficiency.

Translated by ChatGPT 5