Random Book Title with Substring Constraint

Mivik types his book title by randomly pressing keys on a keyboard with m distinct keys. He will make n keystrokes, each key chosen uniformly at random. However, he wants the resulting title to contain a given name S as a substring. Your task is to compute the probability that the random title contains S as a substring. Since the answer is a rational number and Mivik dislikes ugly decimals, output the probability modulo 998244353.

More formally, let the total number of strings of length n over an alphabet of size m be mⁿ, and let A be the number of such strings that contain S as a substring. You should output

[ P = A \cdot (m^n)^{-1} \mod 998244353, ]

where the inverse is taken modulo 998244353, and all computations are performed modulo 998244353.

Note: It is guaranteed that the characters of S are among the m distinct keys on the keyboard. In other words, if we denote by K the set of characters in S, then |K|≤m.

inputFormat

The input consists of two lines. The first line contains two integers n and m (the number of keystrokes and the size of the keyboard, respectively). The second line contains the string S, representing the required substring in the title.

For example:

3 3
ab

outputFormat

Output a single integer: the probability that a randomly typed title of length n (using an alphabet of size m) contains S as a substring, modulo 998244353.

sample

3 3
ab

887328314