Oppgave

For et heltall $n$ ($1 \le n$) kalles strengen som dannes ved å veksle mellom $n+1$ stykk 'I' og $n$ stykk 'O' med start på 'I' for $P_n$. Her er 'I' og 'O' store engelske bokstaver.

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

Figur 1-1: Strengen $P_n$ for et heltall $n$ ($1 \le n$)

Gitt et heltall $n$ og en streng $s$ som kun består av 'I' og 'O', skriv et program som skriver ut på hvor mange steder i strengen $s$ strengen $P_n$ finnes.

Inndata

Inndataene består av $3$ linjer: - På linje $1$ står et heltall $n$ ($1 \le n \le 1000000$). - På linje $2$ står et heltall $m$ ($1 \le m \le 1000000$), der $m$ angir antall tegn i strengen $s$. - På linje $3$ står strengen $s$, som kun består av 'I' og 'O'.

For alle testdata gjelder $2n + 1 \le m$. I tillegg gjelder $n \le 100$ og $m \le 10000$ for $50\%$ av poengene.

Utdata

Skriv ut $1$ linje som kun inneholder et heltall som angir på hvor mange steder i strengen $s$ strengen $P_n$ finnes. Hvis $P_n$ ikke finnes i $s$, skriv ut heltallet $0$.

Sample 1

1
13
OOIOIOIOIIOII

4

Sample 2

2
13
OOIOIOIOIIOII

2

Forklaring av eksempler

Når heltallet $n$ er $1$ og strengen $s$ er OOIOIOIOIIOII, finnes strengen $P_1$, altså IOI, på $4$ steder slik det vises i Figur 1-2 nedenfor, så heltallet som skal skrives ut er $4$.

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

Figur 1-2: I Eksempel 1 finnes strengen $P_1$ på $4$ steder

Når heltallet $n$ er $2$ og strengen $s$ er OOIOIOIOIIOII, finnes strengen $P_2$, altså IOIOI, på $2$ steder slik det vises i Figur 1-3 nedenfor, så heltallet som skal skrives ut er $2$.

OOIOIOIOIIOII
  ^^^^^
    ^^^^^

Figur 1-3: I Eksempel 2 finnes strengen $P_2$ på $2$ steder