codeforces#P1580F. Problems for Codeforces
Problems for Codeforces
Description
XYMXYM and CQXYM will prepare $n$ problems for Codeforces. The difficulty of the problem $i$ will be an integer $a_i$, where $a_i \geq 0$. The difficulty of the problems must satisfy $a_i+a_{i+1}<m$ ($1 \leq i < n$), and $a_1+a_n<m$, where $m$ is a fixed integer. XYMXYM wants to know how many plans of the difficulty of the problems there are modulo $998\,244\,353$.
Two plans of difficulty $a$ and $b$ are different only if there is an integer $i$ ($1 \leq i \leq n$) satisfying $a_i \neq b_i$.
A single line contains two integers $n$ and $m$ ($2 \leq n \leq 50\,000$, $1 \leq m \leq 10^9$).
Print a single integer — the number of different plans.
Input
A single line contains two integers $n$ and $m$ ($2 \leq n \leq 50\,000$, $1 \leq m \leq 10^9$).
Output
Print a single integer — the number of different plans.
Samples
3 2
4
5 9
8105
21038 3942834
338529212
Note
In the first test case, the valid $a$ are: $[0,0,0]$, $[0,0,1]$, $[0,1,0]$, $[1,0,0]$.
$[1,0,1]$ is invalid since $a_1+a_n \geq m$.