Énoncé

Pour un entier $n$ ($1 \le n$), la chaîne de caractères formée en alternant $n+1$ lettres 'I' et $n$ lettres 'O' en commençant par 'I' est appelée $P_n$. Ici, 'I' et 'O' sont les lettres majuscules de l'alphabet latin.

• $P_1$: IOI
• $P_2$: IOIOI
• $P_3$: IOIOIOI
• $P_n$: IOIOIO $\cdots$ OI ($n$ lettres 'O')

Figure 1-1 : La chaîne $P_n$ pour un entier $n$ ($1 \le n$)

Étant donné un entier $n$ et une chaîne $s$ composée uniquement de 'I' et de 'O', écrivez un programme qui affiche en combien d'endroits la chaîne $s$ contient la chaîne $P_n$.

Entrée

L'entrée est composée de $3$ lignes : - La $1$-re ligne contient un entier $n$ ($1 \le n \le 1000000$). - La $2$-e ligne contient un entier $m$ ($1 \le m \le 1000000$). $m$ représente le nombre de caractères de la chaîne $s$. - La $3$-e ligne contient la chaîne $s$, composée uniquement de 'I' et de 'O'.

Pour toutes les données de test, $2n + 1 \le m$ est vérifié. De plus, pour $50\%$ des points, $n \le 100$ et $m \le 10000$ sont vérifiés.

Sortie

Affichez $1$ seule ligne contenant uniquement un entier représentant le nombre d'endroits où la chaîne $P_n$ apparaît dans la chaîne $s$. Si la chaîne $P_n$ n'apparaît pas dans $s$, affichez l'entier $0$.

Sample 1

1
13
OOIOIOIOIIOII

4

Sample 2

2
13
OOIOIOIOIIOII

2

Explication des exemples

Lorsque l'entier $n$ vaut $1$ et que la chaîne $s$ est OOIOIOIOIIOII, la chaîne $P_1$, c'est-à-dire IOI, est contenue en $4$ endroits comme indiqué sur la Figure 1-2 ci-dessous ; l'entier à afficher est donc $4$.

OOIOIOIOIIOII
  ^^^
    ^^^
      ^^^
         ^^^

Figure 1-2 : Dans le cas de l'exemple 1, la chaîne $P_1$ est contenue en $4$ endroits

Lorsque l'entier $n$ vaut $2$ et que la chaîne $s$ est OOIOIOIOIIOII, la chaîne $P_2$, c'est-à-dire IOIOI, est contenue en $2$ endroits comme indiqué sur la Figure 1-3 ci-dessous ; l'entier à afficher est donc $2$.

OOIOIOIOIIOII
  ^^^^^
    ^^^^^

Figure 1-3 : Dans le cas de l'exemple 2, la chaîne $P_2$ est contenue en $2$ endroits