406118: GYM102268 K Knowledge

You have a string $$$s$$$ consisting of lowercase English letters "a" and "b".

You can make zero or more operations in any order. Here are the possible operations:

• Delete "aa" from any place of the string.
• Delete "bbb" from any place of the string.
• Delete "ababab" from any place of the string.
• Add "aa" to any place of the string.
• Add "bbb" to any place of the string.
• Add "ababab" to any place of the string.

Your goal is to calculate the number of strings of length $$$x$$$ that can be obtained by such operations. As the answer can be very large, find it modulo $$$998\,244\,353$$$.

The first line of the input contains one integer $$$n$$$: the length of the string ($$$1 \leq n \leq 300\,000$$$).

The second line contains a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters "a" and "b".

The third line contains one integer $$$x$$$ ($$$0 \leq x \leq 10^9$$$), the length of the string you need to obtain.

Print one integer: the number of strings of length $$$x$$$ that can be obtained from string $$$s$$$ by making the operations described above, taken modulo $$$998\,244\,353$$$.

6
ababab
3

1

3
bbb
2

1

5
babab
35

866826000