IOIOI

Let $P_N$ be the string formed from $N+1$ copies of I and $N$ copies of O in which I and O alternate. That is, $P_N$ starts and ends with I, with $N$ Os in between.

• $P_1$ = IOI
• $P_2$ = IOIOI
• $P_3$ = IOIOIOI
• $P_N$ = IOIOI…OI (with $N$ Os)

Given a string $S$ consisting only of I and O and an integer $N$, write a program that counts how many times $P_N$ occurs in $S$. Overlapping occurrences are counted separately.

The first line contains the integer $N$.

The second line contains $M$, the length of the string $S$.

The third line contains the string $S$.

Print, on a single line, how many times $P_N$ occurs in $S$.

• $1 \le N \le 1{,}000{,}000$
• $2N+1 \le M \le 1{,}000{,}000$
• $S$ consists only of I and O.