10978: 解除咒语
[Creator : ]
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 取模后输出,以便国王能够安全地使用这些结果。
为了完成这个任务,艾丽丝走进了她的秘密实验室。她拿出了她的魔法书和一卷古老的羊皮纸,开始仔细研究每一个可能的序列组合。她的魔法帮助她在心中描绘出所有可能的序列,并验证它们是否满足国王给出的条件。
艾丽丝日以继夜地工作着,列出并计算出所有符合条件的序列。每当她发现一个符合条件的序列,她就会在纸上记下它,并将其总和进行模运算,以防止数据过于庞大。
经过不懈的努力,艾丽丝终于找出了所有可能的序列。当她把结果呈给国王时,国王大为震惊。原来,王国有如此多的未来可能性,而艾丽丝的智慧和辛勤工作为王国的未来指明了方向。
国王告诉艾丽丝,王国的未来正受到一个强大咒语的威胁。这个咒语隐藏在一个神秘的序列中,这个序列由 $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$
$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