Counting Sequence

Time limit16sMemory limit1024 MB

Summary

Count sequences of positive integers with adjacent differences of 1 and sum n, weighting each by c raised to the number of descents, modulo 998244353.

Level: Hard8 of 10
Topics: Dynamic programming, Math, Combinatorics
Solved: No attempts yet

Problem

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 sequence $a_1, a_2, \ldots, a_m$ , define

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

That is, $f(a)$ is the number of indices $i$ with $1 \leq i \leq m-1$ such that $a_i > a_{i+1}$ . The weight of a sequence $a$ is $c^{f(a)}$ .

Compute the sum of the weights of all good sequences, modulo 998244353.

Input

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

Output

Output the answer modulo 998244353.

Hint

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

Examples3

Example 1
Input
```
5 3
```
Expected output
```
8
```
Example 2
Input
```
1 0
```
Expected output
```
1
```
Example 3
Input
```
2022 39
```
Expected output
```
273239559
```