P8158 "PMOI-5" Component Forces

There is a circle with radius $1$ and center at $(0,0)$ on the Cartesian plane. On this circle, $n$ red points are marked at equal distances, and one of the points lies on the positive $x$-axis. NaCly\_Fish is also at $(0,0)$. She randomly chooses a red point with equal probability and pushes toward it with a force of $1 \text N$. Let the components of her pushing force on the $x$ and $y$ axes be $F_x$ and $F_y$. She wants to know the $k$-th central moments of these two random variables. For a random variable $x$, its $k$-th central moment is defined as $E((x-E(x))^k)$, where $E(x)$ is the expected value of $x$. It can be proved that the answer **must be a rational number**, so output the answer modulo $998244353$.

Input one line with two positive integers $n, k$.

Output one line with two integers, representing the $k$-th central moments of $F_x$ and $F_y$, respectively.

[Explanation for Sample 1] The second central moment is the variance. Since she can only push in the positive or negative $x$ direction, $F_y$ is always zero, so its variance is also zero. $F_x$ can be $\pm 1$ with equal probability, so the variance is $1$. [Constraints] **This problem uses bundled testdata.** - Subtask 1 (7 pts): $2\le n,k \le 20$; - Subtask 2 (14 pts): $2\le n \le 100$; - Subtask 3 (19 pts): $2\le n \le 10^3$; - Subtask 4 (23 pts): $2\le k \le 10^7$; - Subtask 5 (37 pts): no special restrictions. For $100\%$ of the testdata, $2\le n \le 3 \times 10^4$ and $2\le k \le 10^9$. Translated by ChatGPT 5