Problems for Codeforces

8000ms

262144K

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

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.

Sample Input:

3 2

Sample Output:

Sample Input:

5 9

Sample Output:

Sample Input:

21038 3942834

Sample Output:

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

Informação

Provedor Codeforces

Código CF1580F