25659번 - Counting Sequence 다국어

문제

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円$.

제한

힌트

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

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