Description

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 Format

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

Output Format

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

2 2

1 0

5 15

815216641 0

114 514

636199406 569855248

Hint

[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