题目描述
小 N 在收拾老家阁楼时,翻出了一张祖传的秘制酱汁配方。
这张配方非常古怪。它一共涉及 n+1 种调料(编号从 0 到 n),而且每种调料的用量只有两种状态:1 表示放一勺,0 表示不放。因此,整张配方可以用一串长长的 0 和 1 构成的序列 f(x) 来表示。
这种复合酱汁是由两种不同的基础配方 p(x) 和 q(x) 融合出来的。不过这里的风味融合规则有点奇特:如果配方 p 里的第 i 号调料,遇上了配方 q 里的第 j 号调料,它们就会碰撞组合成一种全新的第 i+j 号风味。
而且,厨房里存在“物极必反”的铁律:在所有调料大融合之后,如果某种风味被重复生成了偶数次,它的味道就会因为相互冲突而彻底蒸发(变成 0);只有被生成了奇数次的风味,才能最终在酱汁里留下来(变成 1)。
可以发现,这个过程和mod2 下的多项式乘法完全一致! f(x) 事实上就是一个 n 次的多项式。
现在,小 N 手里拿着祖传配方 f(x)。他很好奇:在满足这种厨房规律的前提下,市面上到底能有多少种不同的“子配方” p(x),可以通过和别的配方混合,恰好把这个祖传秘方给调配出来?
由于答案可能很大,你只需要输出子配方总数对 998244353 取模后的结果即可。
输入格式
第一行包含两个正整数 type 和 n,其中 n 表示多项式的次数,type 的含义详见数据范围。
第二行包含 n+1 个零或一的数字,从低到高表示多项式 f(x) 的各项系数,保证 f(x) 最高项系数为 1。
输出格式
一行一个整数表示答案。
样例 1
1 2
1 0 1
3
样例 1 解释
共有 1,1+x,1+x2 三个因式。其中 (1+x)2≡1+x2(mod2)。
样例 2
1 15
0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 1
12
数据范围与约定
对于 100% 的测试数据,1≤n≤2000。
Subtask1(20%):type=1,n≤15。
Subtask2(20%):type=2,保证 f(x)=gk(x),其中 g(x) 是个因式个数为 2 的式子。
Subtask3(20%):type=3,保证 f(x) 不含平方因子,即不存在非零次多项式 g(x),使得 g(x)2 是个因式。
Subtask4(20%):type=4,n≤200。
Subtask5(20%):type=5,无特殊限制。