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

数据范围

1. (20pts) $m\le 20$
2. (30pts) $m\le 500$
3. (50pts) $m\le 3000$