题目描述

给定初始字符串为 1。

定义一次变换操作如下：将当前字符串中的每一个字符独立替换为它的二次幂的十进制表示，即：

$$1 \to 2,\quad 2 \to 4,\quad 4 \to 16,\quad 6 \to 64$$

例如：

• 第 $0$ 秒时字符串为 1
• 第 $1$ 秒时字符串为 2
• 第 $2$ 秒时字符串为 4
• 第 $3$ 秒时字符串为 16
• 第 $4$ 秒时字符串为 264

给定整数 $n$ 和模式串 $S$，请你求出：第 $n$ 秒生成的字符串中，模式串 $S$ 作为连续子串出现了多少次。

答案对模数$998244353$取模后输出。

输入格式

输入共两行。

第一行一个整数 n。

第二行一个字符串 S。

设 $m = |S|$，对于所有数据，满足：

$$0 \le n \le 10^9$$ $$1 \le m \le 10^5$$

字符串 $S$ 仅由字符 1、2、4、6 组成。

输出格式

输出一个整数，表示答案对 998244353 取模后的结果。

9
26

5

2020
16

292008622