Xét một xâu có độ dài $N$. Gọi $S$ là xâu đó được lặp lại $K$ lần. Bạn quan tâm đến độ "WAC" của xâu này, vì vậy nhiệm vụ của bạn là tìm độ WAC của xâu đó.

Độ WAC của một xâu là số lần "WAC" xuất hiện dưới dạng một xâu con (subsequence) của xâu đó.

Một xâu con của một xâu là một xâu có thể thu được từ xâu đã cho bằng cách xóa đi không hoặc nhiều ký tự mà không làm thay đổi thứ tự của các ký tự còn lại. Hai xâu con được coi là khác nhau nếu có ít nhất một chỉ số còn lại khác nhau. Ví dụ, trong xâu "AABC", xâu con được tạo bởi các chỉ số 1, 3 và 4 khác với xâu con được tạo bởi các chỉ số 2, 3 và 4.

Vì kết quả có thể rất lớn, hãy in ra kết quả theo modulo $998\,244\,353$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $K$ ($1 \le N \le 200\,000$, $1 \le K \le 200\,000$), độ dài của xâu ban đầu và số lần xâu đó được lặp lại để tạo thành $S$. Dòng thứ hai và cũng là dòng cuối cùng chứa xâu ban đầu gồm $N$ ký tự, bao gồm các chữ cái in hoa trong bảng chữ cái tiếng Anh.

Dữ liệu ra

In ra độ WAC của xâu $S$ theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

5 1
WABCA

Dữ liệu ra 1

1

Dữ liệu vào 2

5 2
WABCA

Dữ liệu ra 2

5