CF1580F.Problems for Codeforces

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} \lt m$ ($1 \leq i \lt n$), and $a_1+a_n \lt 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$.

XYMXYM 和 CQXYM 将为 Codeforces 准备 $n$ 道题目。第 $i$ 道题的难度为一个整数 $a_i$，其中 $a_i \geq 0$。题目的难度需满足约束条件：对所有 $1 \leq i < n$，有 $a_i + a_{i+1} < m$，且 $a_1 + a_n < m$，其中 $m$ 是一个给定的固定整数。XYMXYM 想知道满足上述条件的难度设定方案总数，答案对 $998\,244\,353$ 取模。

若存在某个整数 $i$（$1 \leq i \leq n$）使得 $a_i \neq b_i$，则称两个难度序列 $a$ 和 $b$ 是不同的。

A single line contains two integers $n$ and $m$ ($2 \leq n \leq 50\,000$, $1 \leq m \leq 10^9$).

一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 50\,000$，$1 \leq m \leq 10^9$）。

Print a single integer — the number of different plans.

输出一个整数——不同方案的数量。

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

在第一个测试用例中，合法的 $a$ 有：$[0,0,0]$、$[0,0,1]$、$[0,1,0]$、$[1,0,0]$。

$[1,0,1]$ 不合法，因为 $a_1+a_n \geq m$。