Problem10978--解除咒语

10978: 解除咒语

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

在遥远的数学王国里,有一位名叫艾丽丝的年轻女巫。她非常聪明,总是能解决别人无法理解的难题。一天,国王召见了她,并给她布置了一项艰巨的任务。

国王告诉艾丽丝,王国的未来正受到一个强大咒语的威胁。这个咒语隐藏在一个神秘的序列中,这个序列由 N 个整数 A 组成,它们必须满足以下几个严格的条件:

$0≤A_i\ (i=1,2,…,N)$

$\sum_{i=1}^{N} A_i$

$A_1\ \text{xor}\ A_2\ \text{xor}\ ⋯\ \text{xor} A_N=0$

("xor" 表示按位异或操作)

“这个咒语非常复杂,它蕴含的力量足以改变整个王国的命运。”国王说道,“你的任务是找到满足这些条件的所有可能的序列。每一个序列代表了我们王国的一种可能未来,只有当你找出所有可能的序列时,我们才能知道哪些未来是安全的。”

艾丽丝知道这个任务的艰巨。她思索了片刻,决定用她的魔法和智慧来应对这项挑战。她意识到,仅仅找到这些序列还不够,因为结果可能会非常巨大,甚至难以处理。因此,她需要将答案模 998244353 取模后输出,以便国王能够安全地使用这些结果。

为了完成这个任务,艾丽丝走进了她的秘密实验室。她拿出了她的魔法书和一卷古老的羊皮纸,开始仔细研究每一个可能的序列组合。她的魔法帮助她在心中描绘出所有可能的序列,并验证它们是否满足国王给出的条件。

艾丽丝日以继夜地工作着,列出并计算出所有符合条件的序列。每当她发现一个符合条件的序列,她就会在纸上记下它,并将其总和进行模运算,以防止数据过于庞大。

经过不懈的努力,艾丽丝终于找出了所有可能的序列。当她把结果呈给国王时,国王大为震惊。原来,王国有如此多的未来可能性,而艾丽丝的智慧和辛勤工作为王国的未来指明了方向。

Input

一行, 两个正整数 $n$ 和 $m$。

Output

一行,取模之后的可能性总数。

Constraints

输入中的所有值均为整数。 
$1≤N≤5,000$
$1≤M≤5000$

Sample 1 Input

5 20

Sample 1 Output

475

Sample 2 Input

3141 2718

Sample 2 Output

371899128

Source/Category