IOIOI

Time Limit : 1 sec, Memory Limit : 65536 KB

IOIOI

問題

整数 n (1 ≤ n) に対し, n + 1 個の In 個の OI から始めて交互に並べてできる文字列を Pn とする.ここで IO はそれぞれ英大文字のアイとオーである.


P1

IOI

P2

IOIOI

P3

IOIOIOI
.
.
.

Pn

IOIOIO ... OI (On 個)

図 1-1 本問で考える文字列 Pn


整数 n と, I と O のみからなる文字列 s が与えられた時, s の中に Pn が何ヶ所含まれているかを出力するプログラムを作成せよ.

n が 1, sOOIOIOIOIIOII の場合, P1IOI であり,下図 1-2 に示した 4ヶ所に含まれている.よって,出力は 4 である.

OOIOIOIOIIOII
OOIOIOIOIIOII
OOIOIOIOIIOII
OOIOIOIOIIOII

図 1-2 n が 1, sOOIOIOIOIIOII の場合の例

n が 2, sOOIOIOIOIIOII の場合, P2IOIOI であり,下図 1-3 に示した 2ヶ所に含まれている.よって,出力は 2 である.

OOIOIOIOIIOII
OOIOIOIOIIOII

図 1-3 n が 2, sOOIOIOIOIIOII の場合の例

入力

入力ファイルのファイル名は input.txt である.
1 行目には整数 n (1 ≤ n ≤ 1000000) が書かれている.
2 行目には整数 m (1 ≤ m ≤ 1000000) が書かれている. ms の文字数を表す.
3 行目には文字列 s が書かれている. sIO のみからなる.

全ての採点用データで, 2n + 1 ≤ m である.採点用データのうち, 配点の 50% 分については, n ≤ 100, m ≤ 10000 を満たす.

出力

出力ファイルのファイル名は output.txt である.
output.txt は,文字列 s に文字列 Pn が何ヶ所含まれるかを表す 1 つの整数を含む 1 行からなる.

sPn が含まれていない場合は,整数として 0 を出力せよ.

入出力の例

例1

input.txt

1
13
OOIOIOIOIIOII

output.txt

4

例2

input.txt

2
13
OOIOIOIOIIOII

output.txt

2

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。

Notes on Submission

標準入出力を行うプログラムを作成して下さい.

上記形式で複数のデータセットが与えられます. n が 0 のとき入力の終わりを示します.

Sample Input

1
13
OOIOIOIOIIOII
2
13
OOIOIOIOIIOII
0

Sample Output

4
2

Source: 8th Japanese Olympiad in Informatics , 2009-02-08
http://www.ioi-jp.org/