Codeforces Round 745 (Div. 1) |
---|

Finished |

combinatorics

fft

math

*3300

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Problems for Codeforces

time limit per test

8 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputXYMXYM 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.

Examples

Input

3 2

Output

4

Input

5 9

Output

8105

Input

21038 3942834

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/19/2024 19:34:30 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|