← 返回题目列表

Codeforces · 1580/F

F. Codeforces 的问题

中文机器翻译题面 查看原题

XYMXYM 和 CQXYM 将为 Codeforces 准备 $$$n$$$ 问题。问题$$$i$$$的难度将是一个整数$$$a_i$$$,其中$$$a_i \geq 0$$$。问题的难度必须满足$$$a_i+a_{i+1}<m$$$ ($$$1 \leq i < n$$$),并且$$$a_1+a_n<m$$$,其中$$$m$$$是固定整数。 XYMXYM 想知道问题的难度有多少个以 $$$998\,244\,353$$$ 为模的计划。

仅当存在满足 $$$a_i \neq b_i$$$ 的整数 $$$i$$$ ($$$1 \leq i \leq n$$$) 时,两个难度计划 $$$a$$$ 和 $$$b$$$ 才不同。

输入

单行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 50\,000$$$, $$$1 \leq m \leq 10^9$$$)。

输出

打印一个整数——不同计划的数量。

示例

输入 #1

3 2

输出 #1

4

输入 #2

5 9

输出 #2

8105

输入 #3

21038 3942834

输出 #3

338529212

注意

在第一个测试用例中,有效的 $$$a$$$ 为:$$$[0,0,0]$$$、$$$[0,0,1]$$$、$$$[0,1,0]$$$、$$$[1,0,0]$$$。

$$$[1,0,1]$$$ 无效,因为 $$$a_1+a_n \geq m$$$。