Problem Description

Given positive integers $N$ and $M$. Find the number of sequences $a$ of length $N$ where each element is between $1$ and $M$ (inclusive) that satisfy the following condition, modulo $998244353$:

• There is no contiguous subsequence of $a$ with length 2 or more that is a palindrome.

Input Format

The input is given from the standard input in the following format:

$N$ $M$

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

2 2

Sample Output #1

2

Sample Input #2

3 3

Sample Output #2

6

Sample Input #3

314 159

Sample Output #3

809839613

Notes/Hints

Constraints

• $2 \le N \le 10^{12}$
• $1 \le M \le 10^{12}$
• All inputs are integers

Sample Explanation 1

The sequences $a=(1,2)$ and $a=(2,1)$ satisfy the condition.

Sample Explanation 3

Remember to find the answer modulo $998244353$. Original idea: turtle0123__

见题面 Input 部分

见题面 Output 部分