지식

영소문자 “a”와 “b”로 이루어진 문자열 $s$가 주어진다.

다음 연산을 원하는 순서로 0번 이상 수행할 수 있다.

• 문자열의 임의 위치에서 “aa”를 지운다.
• 문자열의 임의 위치에서 “bbb”를 지운다.
• 문자열의 임의 위치에서 “ababab”를 지운다.
• 문자열의 임의 위치에 “aa”를 넣는다.
• 문자열의 임의 위치에 “bbb”를 넣는다.
• 문자열의 임의 위치에 “ababab”를 넣는다.

이 연산들로 얻을 수 있는 길이 $x$인 문자열의 개수를 구하시오. 답이 매우 클 수 있으므로 998 244 353으로 나눈 나머지를 구한다.

첫째 줄에 문자열의 길이 $n$이 주어진다. ($1 \le n \le 300\,000$)

둘째 줄에 영소문자 “a”와 “b”로 이루어진 길이 $n$의 문자열 $s$가 주어진다.

셋째 줄에 얻어야 하는 문자열의 길이 $x$가 주어진다. ($0 \le x \le 10^9$)

문자열 $s$에서 위 연산들을 수행해 얻을 수 있는 길이 $x$인 문자열의 개수를 998 244 353으로 나눈 나머지를 출력한다.