A. Analyzing the Race
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Maxwell, a great enthusiast of all forms of racing, decided to organize the UnBalloon World Kart Championship! In this championship, the best drivers from the group were chosen, each representing the initial of their name, meaning that $$$26$$$ competitors were selected, one for each letter of the alphabet. These competitors will have to compete for $$$n$$$ exciting laps, vying for the legendary title of felipe_massa.

The great journalist and photographer Isa decided to write an article about this event. However, caught up in all the competition and excitement of the race, she only managed to record the winners of $$$m$$$ consecutive laps! Isa cannot remember when she started making these notes, but she is sure that they are correct and occurred at some point during the race, and that each letter represents which driver won that lap. To finish her article, she needs to know how many ways the race as a whole could have occurred following her notes, knowing that a race is characterized only by the winners of each lap.

Thus, it is up to you, an aspiring titleholder of felipe_massa and a racing enthusiast, to answer this question. Since the number of distinct races can be very large, Isa asked that this calculation be performed modulo $$$998244353$$$. Two races are considered different if, in some lap $$$i$$$, the winner of that lap $$$i$$$ is different between the races.

Input

The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^{18}$$$, $$$1 \leq m \leq 100$$$, $$$m \leq n$$$), the total number of laps and the size of Isa's notes.

The second line contains a string $$$s$$$, the race notes, composed of $$$m$$$ lowercase characters from the Latin alphabet.

Output

Print the number of races that could have occurred according to Isa's notes, modulo $$$998244353$$$.

Examples
Input
6 5
ilprw
Output
52
Input
8 5
ababa
Output
70252
Input
100000000 15
novofelipemassa
Output
966021064
Note

In the first test case, Isa wrote down the results of $$$5$$$ laps, with the winners of each lap being "ilprw". Since the race had a total of $$$6$$$ laps, the races "$$$X$$$ilprw" or "ilprw$$$X$$$" could have occurred, where $$$X$$$ represents any of the $$$26$$$ competitors.