Code
TL : 1s
ML : 512MB
题目描述
mas在做看Computer Science:An overview的时候，看到了对文本进行编码的方法，文中提到了哈弗曼编码，海明距离等概念，mas突发奇想，想到了一种奇特的文本加密方式。
一开始，他有一个长度为n的01串$s$，然后他采取以下方式对字符串进行加密：
根据串$s$，mas可以得到一个长度为$k$的序列$a_1,a_2,\dots,a_k$，如果s[1]=1，那么表示$s$由$a_1$个1,$a_2$个$0$，$a_3$个$1$……按顺序拼接而成，否则如果s[1]=0，那么表示$s$由$a_1$个0,$a_2$个$1$，$a_3$个$0$……按顺序拼接而成。然后，mas将每个数字表示成二进制数字，按顺序拼接得到字符串$t$，字符串$t$即为对$s$进行加密得到的结果。
举个例子，$s=1101000$，那么$ k=4,a_1=2,a_2=1,a_3=1,a_4=3$，将$a_1,a_2,a_3,a_4$转化成二进制可以得到$10,1,1,11$，按顺序拼接得到$t=101111$，那么$101111$即为对$1101000$进行加密得到的结果。
现在mas费尽千辛万苦得到了加密后的字符串t，但是他忘记初始的$s$是什么了，只记得$s$的长度不超过$m$，他想知道初始有多少种不同的s满足条件。
输入
第一行一个整数$m$，表示$s$的长度不超过$m$
第二行一个字符串$t$，保证$t$的长度不超过$m$
输出
由于答案可能很大，请输出答案对998244353取模的结果。
样例输入1
20
1100111110
样例输出1
44
数据范围
- (20pts) $m\le 20$
- (30pts) $m\le 500$
- (50pts) $m\le 3000$
