001 - IOIOI (IOIOI)

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / x 4 /


TLE
1sec
MLE
64MB
得点
100

問題

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

P1IOI
P2IOIOI
P3IOIOIOI
::
PnIOIOIO...OI (O が n 個)

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

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

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

OOIOIOIOIIOII
OOIOIOIOIIOII
OOIOIOIOIIOII
OOIOIOIOIIOII

図 1-2 n が 1, s が OOIOIOIOIIOII の場合の例

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

OOIOIOIOIIOII
OOIOIOIOIIOII

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

入力

 標準入力から以下の入力を読み込め.

  • 1 行目には整数 n (1 ≤ n ≤ 1000000) が書かれている.
  • 2 行目には整数 m (1 ≤ m ≤ 1000000) が書かれている. ms の文字数を表す.
  • 3 行目には文字列 s が書かれている. s は I と O のみからなる.

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

出力

 文字列 s に文字列 Pn が何ヶ所含まれるかを表す 1 つの整数を含む 1 行からなる.
 sPn が含まれていない場合は, 整数として 0 を出力せよ.

入出力例

入力例 1

1
13
OOIOIOIOIIOII

出力例 1

4

入力例 2

2
13
OOIOIOIOIIOII

出力例 2

2