Problema

Per un intero $n$ ($1 \le n$), la stringa formata alternando $n+1$ lettere 'I' e $n$ lettere 'O' iniziando con 'I' è chiamata $P_n$. Qui, 'I' e 'O' sono lettere maiuscole dell'alfabeto inglese.

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

Figura 1-1: La stringa $P_n$ per un intero $n$ ($1 \le n$)

Dati un intero $n$ e una stringa $s$ composta esclusivamente da 'I' e 'O', scrivi un programma che stampi in quanti punti della stringa $s$ è contenuta la stringa $P_n$.

Dati di input

L'input è composto da $3$ righe: - Nella $1$-a riga è scritto un intero $n$ ($1 \le n \le 1000000$). - Nella $2$-a riga è scritto un intero $m$ ($1 \le m \le 1000000$), dove $m$ rappresenta il numero di caratteri della stringa $s$. - Nella $3$-a riga è scritta la stringa $s$, composta esclusivamente da 'I' e 'O'.

In tutti i dati di test vale $2n + 1 \le m$. Inoltre, per il $50\%$ del punteggio vale $n \le 100$ e $m \le 10000$.

Dati di output

Stampa $1$ sola riga contenente unicamente un intero che rappresenta in quanti punti della stringa $s$ è contenuta la stringa $P_n$. Se la stringa $P_n$ non è contenuta in $s$, stampa l'intero $0$.

Sample 1

1
13
OOIOIOIOIIOII

4

Sample 2

2
13
OOIOIOIOIIOII

2

Spiegazione degli esempi

Quando l'intero $n$ è $1$ e la stringa $s$ è OOIOIOIOIIOII, la stringa $P_1$, ovvero IOI, è contenuta in $4$ punti come mostrato nella Figura 1-2 qui sotto, quindi l'intero da stampare è $4$.

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

Figura 1-2: Nel caso dell'Esempio 1, la stringa $P_1$ è contenuta in $4$ punti

Quando l'intero $n$ è $2$ e la stringa $s$ è OOIOIOIOIIOII, la stringa $P_2$, ovvero IOIOI, è contenuta in $2$ punti come mostrato nella Figura 1-3 qui sotto, quindi l'intero da stampare è $2$.

OOIOIOIOIIOII
  ^^^^^
    ^^^^^

Figura 1-3: Nel caso dell'Esempio 2, la stringa $P_2$ è contenuta in $2$ punti