Description

Country A is a country that likes repetition. In this country, a basic sentence can be represented by a lowercase letter string of length exactly $m$. To show their love for repetition, people in Country A always repeat the sentence they want to express infinitely many times.

Sometimes, such repetition is meaningful. People in Country A call a lowercase letter string that is lexicographically smaller than the 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., lowercase letter strings of length exactly $m$) can, after being repeated infinitely, contain at least one meaningful semantic fragment?

Input Format

The first line of the input file is a positive integer $m$, which denotes the length of the basic sentence. The second line is a lowercase letter string $s$, whose meaning is described above.

Output Format

Output one line with one integer, the number of basic sentences that satisfy the condition. To avoid the answer being too large, you only need to output the result modulo $998244353$.

3
abc

79

5
zxcvb

11881375

20
uuopacpertklmqwbfixc 

765676850

Hint

Let the length of string $s$ be $n$. Then the constraints of $n$ and $m$ follow the table below:

For $100\%$ of the testdata, it is guaranteed that $1\le n,m\le 2000$.

Translated by ChatGPT 5