The Day of Going to the Training Camp

Time limit1sMemory limit1024 MB

Summary

Count sequences of length N over values 1..M that avoid any local peak (a[i-1] < a[i] > a[i+1]), modulo 998244353.

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

Problem

On the day of going to the training camp, Ukje suddenly wondered. Why is the training camp in Nonsan? Why why?

The reason is…

Nonsan (non-san) is not a mountain (san). A sequence $a_1, a_2, a_3$ of length 3 is a mountain if $a_1 < a_2 > a_3$ . A sequence is a nonsan if no three adjacent terms form a mountain. In other words, for a sequence $a$ of length $N$ , there is no index $i$ with $2 \le i < N$ and $a_{i-1} < a_i > a_{i+1}$ .

Let us find out how many nonsan sequences there are.

Input

The first line gives $N$ and $M$ .

Output

Among all sequences of length $N$ made of integers from $1$ to $M$ , print the number of nonsan sequences modulo $998\,244\,353$ .

Constraints

$1 \le N \le 1\,000$
$1 \le M \le 100$

Examples2

Example 1
Input
```
2 100
```
Expected output
```
10000
```
Example 2
Input
```
3 2
```
Expected output
```
7
```