P1371 NOI Yuandan

Xiao A plans to start refining the $\texttt{NOI}$ "Yuandan" (whatever that is). It is said that taking it can improve one’s performance in $\texttt{NOI}$. Here is how it is refined. The Yuandan has three kinds of cores: `N`, `O`, and `I`. There are many such cores arranged in a line in order. During refinement, he picks, from left to right, an `N`, then an `O`, then an `I`, and swallows them. Now he wonders how many ways there are to take it... Hold on! He feels the number of ways is too few to become immortal. So he can, by some means, obtain any one of the three types of cores `N`, `O`, `I` (he may choose which type). Then he inserts this acquired core at any position in the line (including before the first and after the last). You need to find, in the new sequence of cores, how many ways there are to take out `N`, `O`, `I`. The letters in the substring do not need to be consecutive.

- The first line contains an integer $N$, the length of the string. - The second line contains a string consisting only of the letters `N`, `O`, and `I`.

Output the maximum number of ways to refine the $\texttt{NOI}$ Yuandan.

Sample explanation: He can obtain an `N` core and add it to the front. ```plain NNOIOI | NNOIOI | NNOIOI | NNOIOI | NNOIOI | NNOIOI ~ ~~ | ~ ~ ~ | ~ ~~ | ~~~ | ~~ ~ | ~ ~~ ``` Constraints: - For 30% of the testdata, $N \le 200$. - For 50% of the testdata, $N \le 2000$. - For 100% of the testdata, $3 \le N \le 10^5$. Translated by ChatGPT 5