길이가 $N$인 문자열을 고려하자. 이 문자열을 $K$번 반복한 문자열을 $S$라고 하자. 당신은 이 문자열이 얼마나 "WAC"한지 관심이 있으며, 따라서 당신의 과제는 이 문자열의 WAC-ness를 구하는 것이다.

문자열의 WAC-ness는 해당 문자열에서 "WAC"가 부분 수열로 나타나는 횟수이다.

부분 수열이란 주어진 문자열에서 0개 이상의 문자를 삭제하여 얻을 수 있는 문자열로, 남은 문자들의 순서는 유지되어야 한다. 두 부분 수열은 선택된 인덱스 중 적어도 하나가 다르면 서로 다른 것으로 간주한다. 예를 들어, 문자열 "AABC"에서 인덱스 1, 3, 4로 구성된 부분 수열은 인덱스 2, 3, 4로 구성된 부분 수열과 다르다.

정답이 매우 클 수 있으므로, $998\,244\,353$으로 나눈 나머지를 출력하라.

입력

첫 번째 줄에는 두 정수 $N$과 $K$ ($1 \le N \le 200\,000$, $1 \le K \le 200\,000$)가 주어지며, 이는 원래 문자열의 길이와 $S$를 만들기 위해 문자열을 반복하는 횟수이다. 두 번째 줄이자 마지막 줄에는 영어 대문자로 구성된 길이 $N$의 원래 문자열이 주어진다.

출력

문자열 $S$의 WAC-ness를 $998\,244\,353$으로 나눈 나머지를 출력하라.

예제

입력 1

5 1
WABCA

출력 1

1

입력 2

5 2
WABCA

출력 2

5