你有一个由小写英文字母 “a” 和 “b” 组成的字符串 $s$。

你可以按任意顺序执行零次或多次以下操作：

• 从字符串的任意位置删除 “aa”。
• 从字符串的任意位置删除 “bbb”。
• 从字符串的任意位置删除 “ababab”。
• 在字符串的任意位置添加 “aa”。
• 在字符串的任意位置添加 “bbb”。
• 在字符串的任意位置添加 “ababab”。

你的目标是计算通过上述操作可以得到的长度为 $x$ 的字符串的数量。由于答案可能非常大，请将其对 $998\,244\,353$ 取模。

输入格式

第一行包含一个整数 $n$：字符串的长度 ($1 \le n \le 300\,000$)。 第二行包含一个长度为 $n$ 的字符串 $s$，由小写英文字母 “a” 和 “b” 组成。 第三行包含一个整数 $x$ ($0 \le x \le 10^9$)，即你需要得到的字符串长度。

输出格式

输出一个整数：通过上述操作可以从字符串 $s$ 得到的长度为 $x$ 的字符串的数量，结果对 $998\,244\,353$ 取模。

样例

样例输入 1

6
ababab
3

样例输出 1

1

样例输入 2

3
bbb
2

样例输出 2

1

样例输入 3

5
babab
35

样例输出 3

866826000