Knowledge

Time limit1sMemory limit512 MB

Summary

Count strings of length x reachable from s by inserting or deleting the blocks aa, bbb, and ababab, modulo 998244353.

Level: Hard9 of 10
Topics: String, Combinatorics, Dynamic programming, Math
Solved: No attempts yet

Problem

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.

Input

The first line of the input contains one integer $n$ : the length of the string ( $1 \le n \le 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 \le x \le 10^9$ ), the length of the string you need to obtain.

Output

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.

Examples3

Example 1
Input
```
6
ababab
3
```
Expected output
```
1
```
Example 2
Input
```
3
bbb
2
```
Expected output
```
1
```
Example 3
Input
```
5
babab
35
```
Expected output
```
866826000
```