1988. 尘封的01

Touxinzei 终究无法纯净自己的心,只能眼看自己心爱的女子渐行渐远,从此他让琪露诺将自己的心尘封起来了,在他的世界不再有爱,只剩下了0和1......

/uploads/20230610/1686380406812.jpg

Touxinzei 对于 0011 有着自己的见地,00 代表着不爱,11 代表着爱,他认为 0011 是会相互转换的,即爱与不爱之间是可以互相转换的。

最初,Touxinzei 只有一个二进制数 a=0a=0 。设当前这个二进制数为 axa_x ,那么在一次操作后,这个二进制数会变为 ax+1a_{x+1} ,它是由 axa_x 变化而来的:

  • 原本 axa_x 中的所有 00 替换成 11
  • 原本 axa_x 中的所有 11 替换成 1010

我们将最初的二进制数 00 称为 a0a_0 ,第 nn 个生成出来的二进制数称为 ana_n ,那么前几个数如下:

nnana_n
00
11
210
3101
410110
510110101
61011010110110

现在给定了一个 0101pp 和一个数字 nn ,Touxinzei 想知道 ppana_n 中出现的次数,输出可能过大,请你将答案对 998244353998244353 取模。

输入

输入一行一个整数 nn ( 0n1000\leq n\leq 100 ) ,含义如题目所示。

接下来输入一行一个只包含 0011 的字符串 pp ,长度不超过 10510^5

输出

输出一行一个整数表示答案。

样例

标准输入 复制文本
0
1
标准输出 复制文本
0
标准输入 复制文本
6
10
标准输出 复制文本
5
标准输入 复制文本
6
101
标准输出 复制文本
4
登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 42
通过 10