Deskripsi Masalah

Untuk sebuah bilangan bulat $n$ ($1 \le n$), string yang dibentuk dengan menyusun secara bergantian $n+1$ huruf 'I' dan $n$ huruf 'O' dimulai dengan 'I' disebut $P_n$. Di sini, 'I' dan 'O' adalah huruf kapital bahasa Inggris.

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

Gambar 1-1: String $P_n$ untuk bilangan bulat $n$ ($1 \le n$)

Diberikan bilangan bulat $n$ dan sebuah string $s$ yang hanya terdiri dari 'I' dan 'O', buatlah program yang mencetak berapa banyak tempat di dalam string $s$ yang memuat string $P_n$.

Format Masukan

Masukan terdiri dari $3$ baris: - Baris ke-$1$ berisi sebuah bilangan bulat $n$ ($1 \le n \le 1000000$). - Baris ke-$2$ berisi sebuah bilangan bulat $m$ ($1 \le m \le 1000000$). Di sini $m$ menyatakan banyaknya karakter dalam string $s$. - Baris ke-$3$ berisi string $s$ yang hanya terdiri dari 'I' dan 'O'.

Pada semua data uji, berlaku $2n + 1 \le m$. Selain itu, untuk $50\%$ dari total nilai, berlaku $n \le 100$ dan $m \le 10000$.

Format Keluaran

Keluarkan $1$ baris yang hanya berisi sebuah bilangan bulat yang menyatakan berapa banyak tempat di dalam string $s$ yang memuat string $P_n$. Jika $P_n$ tidak termuat di dalam $s$, keluarkan bilangan bulat $0$.

Sample 1

1
13
OOIOIOIOIIOII

4

Sample 2

2
13
OOIOIOIOIIOII

2

Penjelasan Contoh

Ketika bilangan bulat $n$ adalah $1$ dan string $s$ adalah OOIOIOIOIIOII, string $P_1$ yaitu IOI termuat di $4$ tempat seperti ditunjukkan pada Gambar 1-2 di bawah ini, sehingga bilangan bulat yang dikeluarkan adalah $4$.

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

Gambar 1-2: Pada Contoh 1, string $P_1$ termuat di $4$ tempat

Ketika bilangan bulat $n$ adalah $2$ dan string $s$ adalah OOIOIOIOIIOII, string $P_2$ yaitu IOIOI termuat di $2$ tempat seperti ditunjukkan pada Gambar 1-3 di bawah ini, sehingga bilangan bulat yang dikeluarkan adalah $2$.

OOIOIOIOIIOII
  ^^^^^
    ^^^^^

Gambar 1-3: Pada Contoh 2, string $P_2$ termuat di $2$ tempat