P5404 [CTS2019] Repetition

Jia Zhangke said in *Mountains May Depart*, “Life is repetition.” In life, people always like to repeat what they have done. Language is a very classic example. For example, when expressing a question, people are often not satisfied with using just one question mark “?”; using a series of question marks “????” always feels more forceful. When expressing an apology, saying “sorry” once often seems unwilling; repeating it as “sorry sorry” is enough to show sincerity.

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?

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 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$.

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