Migrated from Lutece 2824 01串计数

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给定一个 $01$ 串 $s$，你可以对其进行任意次以下操作：

• 在任意位置删除串 $00$。
• 在任意位置删除串 $111$。
• 在任意位置删除串 $010101$。
• 在任意位置添加串 $00$。
• 在任意位置添加串 $111$。
• 在任意位置添加串 $010101$。

问有多少个长度为 $x$ 的串可以由 $s$ 进行任意次操作（包含0次）得到，答案对 $998244353$ 取模。

Input

第一行一个整数 $n$ 表示 $s$ 的长度，第二行一个 $01$ 串 $s$。

第三行一个整数 $x$。

Output

一行一个整数表示答案。

Samples

6
010101
3

1

3
111
2

1

5
10101
35

866826000

Constraints

$1\le n\le 3\times 10^5, x\le 10^9$.

Resources

2022 UESTC ICPC Training for String and Search Algorithm