Wesley is going on a trip to the North!

But first, he needs a proper runway for takeoff. The runway is marked with festive safety lights and can be represented as a sequence of ~N~ light bulbs repeated ~K~ times, with each safety light lit up with a specific colour. The colour of the light bulbs can each be represented as an uppercase letter, forming a string ~S~ of length ~N~. The complete runway can be represented as a string of length ~N \cdot K~.

Due to the costs associated with maintaining the full runway, Wesley has decided to remove some safety lights. Through careful consideration, the new runway should have exactly ~3~ safety lights forming the pattern WAC. There are many ways to do this, and Wesley is interested in the number of distinct new runways that form the pattern WAC.

The new runway is formed by removing a nonnegative amount of safety lights from the original runway without changing the relative positions of the remaining safety lights. Two runways are considered to be different if there is at least one safety light kept that is located in a different position of the original runway.

As the runway director, please determine and report the number of valid new runways to Wesley! Since the answer could get very large, output the answer modulo ~998\,244\,353~.

Constraints

For this problem, you will be required to pass all the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

~1 \le N,K \le 200\,000~

Subtask 1 [10%]

~1 \le N \le 100~
~1 \le K \le 3~

Subtask 2 [24%]

~1 \le N,K \le 300~

Subtask 3 [66%]

No additional constraints.

Input Specification

The first line will contain two integers ~N~ and ~K~, the number of light bulbs in the pattern ~S~ and the number of repeats of the pattern ~S~ to form the complete runway.

The second and final line will contain a string of ~N~ characters ~S~, consisting of uppercase letters of the alphabet.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output a single integer representing the number of distinct new runways that form the pattern WAC, modulo ~998\,244\,353~.

Sample Input 1

5 1
WABCA

Sample Output 1

1

Sample Explanation 1

The full runway sequence of lights is WABCA.

There is ~1~ way to form a distinct new runway:

• Remove the third and fifth safety light, forming WAC.

Sample Input 2

5 2
WABCA

Sample Output 2

5

Sample Explanation 2

The full runway sequence of lights is WABCAWABCA.

There are ~5~ ways to form a distinct new runway:

• Keep the safety lights at the indices ~1~, ~2~, and ~4~
• Keep the safety lights at the indices ~1~, ~2~, and ~9~
• Keep the safety lights at the indices ~1~, ~5~, and ~9~
• Keep the safety lights at the indices ~1~, ~7~, and ~9~
• Keep the safety lights at the indices ~6~, ~7~, and ~9~