시간 제한메모리 제한제출정답맞힌 사람정답 비율
16 초 (추가 시간 없음) 1024 MB222100.000%

문제

We are given integers $n$ and $c$.

A sequence $a_1, a_2, \ldots, a_m$ is good if and only if:

  • $a_i > 0$ for all $1 \leq i \leq m$,
  • $|a_{i+1}-a_i|=1$ for all $1 \leq i \leq m-1$,
  • $\sum_{i=1}^m a_i=n$.

For a good integer sequence $a_1, a_2, \ldots, a_m$, let us define

$$f(a) = \sum_{i=1}^{m-1} [a_i > a_{i+1}]\text{.}$$

That is, $f(a)$ denotes the number of indices $i$ that satisfy $a_i > a_{i+1}$ among all $1 \leq i \leq m - 1$. We define the weight of the sequence $a$ as the value of $c^{f(a)}$.

Your task is to calculate the sum of the weights of all good sequences, modulo $998\,244\,353$.

입력

The first line contains two integers $n$ and $c$ ($1 \le n \le 3 \cdot 10^5$, $0 \leq c < 998\,244\,353$).

출력

Output the answer modulo $998\,244\,353$.

예제 입력 1

5 3

예제 출력 1

8

예제 입력 2

1 0

예제 출력 2

1

예제 입력 3

2022 39

예제 출력 3

273239559

힌트

In the first example, all good sequences are as follows:

$a$ $f(a)$ $c^{f(a)}$
$[5]$ $0$ $1$
$[2, 3]$ $0$ $1$
$[3, 2]$ $1$ $3$
$[2, 1, 2]$ $1$ $3$

So the answer is $1 + 1 + 3 + 3 = 8$.