Treść zadania

Dla liczby całkowitej $n$ ($1 \le n$), napis utworzony przez naprzemienne ułożenie $n+1$ liter 'I' oraz $n$ liter 'O', zaczynając od 'I', nazywamy $P_n$. Tutaj 'I' oraz 'O' są wielkimi literami alfabetu angielskiego.

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

Rysunek 1-1: Napis $P_n$ dla liczby całkowitej $n$ ($1 \le n$)

Mając daną liczbę całkowitą $n$ oraz napis $s$ składający się wyłącznie z liter 'I' oraz 'O', napisz program, który wypisze, w ilu miejscach w napisie $s$ zawarty jest napis $P_n$.

Wejście

Wejście składa się z $3$ wierszy: - W $1$-szym wierszu znajduje się liczba całkowita $n$ ($1 \le n \le 1000000$). - W $2$-gim wierszu znajduje się liczba całkowita $m$ ($1 \le m \le 1000000$). $m$ oznacza liczbę znaków w napisie $s$. - W $3$-cim wierszu znajduje się napis $s$, składający się wyłącznie z liter 'I' oraz 'O'.

We wszystkich danych testowych zachodzi $2n + 1 \le m$. Ponadto dla $50\%$ punktów zachodzi $n \le 100$ oraz $m \le 10000$.

Wyjście

Wypisz $1$ wiersz zawierający wyłącznie liczbę całkowitą oznaczającą, w ilu miejscach w napisie $s$ zawarty jest napis $P_n$. Jeśli napis $P_n$ nie występuje w $s$, wypisz liczbę całkowitą $0$.

Sample 1

1
13
OOIOIOIOIIOII

4

Sample 2

2
13
OOIOIOIOIIOII

2

Wyjaśnienie przykładów

Gdy liczba całkowita $n$ wynosi $1$, a napis $s$ to OOIOIOIOIIOII, napis $P_1$, czyli IOI, jest zawarty w $4$ miejscach, jak pokazano na Rysunku 1-2 poniżej, więc liczbą całkowitą do wypisania jest $4$.

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

Rysunek 1-2: W przypadku Przykładu 1 napis $P_1$ jest zawarty w $4$ miejscach

Gdy liczba całkowita $n$ wynosi $2$, a napis $s$ to OOIOIOIOIIOII, napis $P_2$, czyli IOIOI, jest zawarty w $2$ miejscach, jak pokazano na Rysunku 1-3 poniżej, więc liczbą całkowitą do wypisania jest $2$.

OOIOIOIOIIOII
  ^^^^^
    ^^^^^

Rysunek 1-3: W przypadku Przykładu 2 napis $P_2$ jest zawarty w $2$ miejscach