Tehtävänanto

Kokonaisluvulle $n$ ($1 \le n$) merkkijonoa, joka muodostuu asettamalla vuorotellen $n+1$ merkkiä 'I' ja $n$ merkkiä 'O' alkaen merkistä 'I', kutsutaan nimellä $P_n$. Tässä 'I' ja 'O' ovat isoja englantilaisia kirjaimia.

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

Kuva 1-1: Merkkijono $P_n$ kokonaisluvulle $n$ ($1 \le n$)

Kun annetaan kokonaisluku $n$ sekä vain merkeistä 'I' ja 'O' koostuva merkkijono $s$, kirjoita ohjelma, joka tulostaa, kuinka monessa kohdassa merkkijonoa $s$ merkkijono $P_n$ esiintyy.

Syöte

Syöte koostuu $3$ rivistä: - Rivillä $1$ on kokonaisluku $n$ ($1 \le n \le 1000000$). - Rivillä $2$ on kokonaisluku $m$ ($1 \le m \le 1000000$), missä $m$ ilmaisee merkkijonon $s$ merkkien lukumäärän. - Rivillä $3$ on merkkijono $s$, joka koostuu vain merkeistä 'I' ja 'O'.

Kaikissaoc-testiaineistoissa pätee $2n + 1 \le m$. Lisäksi $50\%$ pisteistä pätee $n \le 100$ ja $m \le 10000$.

Tuloste

Tulosta $1$ rivi, joka sisältää vain kokonaisluvun: kuinka monessa kohdassa merkkijonoa $s$ merkkijono $P_n$ esiintyy. Jos $P_n$ ei esiinny merkkijonossa $s$ lainkaan, tulosta kokonaisluku $0$.

Sample 1

1
13
OOIOIOIOIIOII

4

Sample 2

2
13
OOIOIOIOIIOII

2

Esimerkkien selitys

Kun kokonaisluku $n$ on $1$ ja merkkijono $s$ on OOIOIOIOIIOII, merkkijono $P_1$ eli IOI esiintyy alla olevan Kuvan 1-2 mukaisesti $4$ kohdassa, joten tulostettava kokonaisluku on $4$.

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

Kuva 1-2: Esimerkin 1 tapauksessa merkkijono $P_1$ esiintyy $4$ kohdassa

Kun kokonaisluku $n$ on $2$ ja merkkijono $s$ on OOIOIOIOIIOII, merkkijono $P_2$ eli IOIOI esiintyy alla olevan Kuvan 1-3 mukaisesti $2$ kohdassa, joten tulostettava kokonaisluku on $2$.

OOIOIOIOIIOII
  ^^^^^
    ^^^^^

Kuva 1-3: Esimerkin 2 tapauksessa merkkijono $P_2$ esiintyy $2$ kohdassa