#P17756. 酱汁秘方

酱汁秘方

题目描述

小 N 在收拾老家阁楼时,翻出了一张祖传的秘制酱汁配方。

这张配方非常古怪。它一共涉及 n+1n+1 种调料(编号从 00 到 nn),而且每种调料的用量只有两种状态:1 表示放一勺,0 表示不放。因此,整张配方可以用一串长长的 0 和 1 构成的序列 f(x)f(x) 来表示。

这种复合酱汁是由两种不同的基础配方 p(x)p(x) 和 q(x)q(x) 融合出来的。不过这里的风味融合规则有点奇特:如果配方 pp 里的第 ii 号调料,遇上了配方 qq 里的第 jj 号调料,它们就会碰撞组合成一种全新的第 i+ji+j 号风味。

而且,厨房里存在“物极必反”的铁律:在所有调料大融合之后,如果某种风味被重复生成了偶数次,它的味道就会因为相互冲突而彻底蒸发(变成 00);只有被生成了奇数次的风味,才能最终在酱汁里留下来(变成 11)。

可以发现,这个过程和 mod 2\bmod2 下的多项式乘法完全一致! f(x)f(x) 事实上就是一个 nn 次的多项式。

现在,小 N 手里拿着祖传配方 f(x)f(x)。他很好奇:在满足这种厨房规律的前提下,市面上到底能有多少种不同的“子配方” p(x)p(x),可以通过和别的配方混合,恰好把这个祖传秘方给调配出来?

由于答案可能很大,你只需要输出子配方总数对 998244353998244353 取模后的结果即可。

输入格式

第一行包含两个正整数 typetype 和 nn,其中 nn 表示多项式的次数,typetype 的含义详见数据范围。

第二行包含 n+1n+1 个零或一的数字,从低到高表示多项式 f(x)f(x) 的各项系数,保证 f(x)f(x) 最高项系数为 11。

输出格式

一行一个整数表示答案。

样例 1

1 2
1 0 1
3

样例 1 解释

共有 1,1+x,1+x21,1+x,1+x^2 三个因式。其中 (1+x)2≡1+x2(mod2)(1+x)^2\equiv 1+x^2\pmod 2。

样例 2

1 15
0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 1
12

数据范围与约定

对于 100%100\% 的测试数据,1≤n≤20001\le n\le 2000。

Subtask⁡1(20%):type=1\operatorname{Subtask}1(20\%):type=1,n≤15n\le 15。

Subtask⁡2(20%):type=2\operatorname{Subtask}2(20\%):type=2,保证 f(x)=gk(x)f(x)=g^k(x),其中 g(x)g(x) 是个因式个数为 22 的式子。

Subtask⁡3(20%):type=3\operatorname{Subtask}3(20\%):type=3,保证 f(x)f(x) 不含平方因子,即不存在非零次多项式 g(x)g(x),使得 g(x)2g(x)^2 是个因式。

Subtask⁡4(20%):type=4\operatorname{Subtask}4(20\%):type=4,n≤200n\le 200。

Subtask⁡5(20%):type=5\operatorname{Subtask}5(20\%):type=5,无特殊限制。