In the film Mountains May Depart, Jia Zhangke says, "Life is repetition." In life, people always like to repeat things they have done. Language is a classic example.
For instance, when expressing doubt, we are never satisfied with using just one question mark "?"; using a string of question marks "????" always seems more powerful.
When expressing an apology, a single "sorry" often seems insincere; repeating "sorry, sorry" is enough to express one's sincerity.
Country A is a country that loves repetition. In this country, a basic sentence can be represented by a string of lowercase letters of length exactly $m$. To express their love for repetition, the people of Country A always like to repeat the sentences they want to express infinitely many times.
Sometimes, such repetition is meaningful. The people of Country A call a lowercase letter string that is lexicographically smaller than a given string $s$ and has the same length as $s$ a "meaningful semantic fragment." They want to know how many different basic sentences (i.e., strings of lowercase letters of length exactly $m$) can be used to find at least one meaningful semantic fragment after being repeated infinitely?
Input
The first line contains a positive integer $m$, representing the length of the basic sentence; the second line contains a lowercase letter string $s$, the meaning of which is detailed in the problem description.
Output
Output a single integer representing the number of basic sentences that satisfy the condition. To avoid an excessively large answer, you only need to output the result modulo $998244353$.
Constraints
Let $n$ be the length of string $s$. The ranges for $n$ and $m$ follow the table below:
| Test Case ID | $m$ | $n$ | Other Constraints |
|---|---|---|---|
| 1 | $m \le 5$ | $n \le 10$ | $m < n$ |
| 2 | $m \le 30$ | $n \le 30$ | $m = n$ |
| 3 | $m \le 50$ | $n \le 30$ | $m > n$ |
| 4 | $m \le 100$ | $n \le 100$ | $m < n$ |
| 5 | $m \le 200$ | $n \le 200$ | $m = n$ |
| 6 | $m \le 300$ | $n \le 200$ | $m > n$ |
| 7 | $m \le 300$ | $n \le 2000$ | $m < n$ |
| 8 | $m \le 1000$ | $n \le 1000$ | $m = n$ |
| 9 | $m \le 2000$ | $n \le 200$ | $m > n$ |
| 10 | $m \le 2000$ | $n \le 2000$ | $m > n$ |
For 100% of the data, it is guaranteed that $1 \le n, m \le 2000$.
Examples
Input 1
3 abc
Output 1
79
Input 2
5 zxcvb
Output 2
11881375