題目描述

對於整數 $n$（$1 \le n$），將 $n+1$ 個 'I' 同 $n$ 個 'O' 由 'I' 開始交替排列所組成嘅字串稱為 $P_n$。呢度嘅 'I' 同 'O' 都係英文大楷字母。

• $P_1$: IOI
• $P_2$: IOIOI
• $P_3$: IOIOIOI
• $P_n$: IOIOIO $\cdots$ OI（共有 $n$ 個 'O'）

圖 1-1：整數 $n$（$1 \le n$）對應嘅字串 $P_n$

畀定整數 $n$ 同埋只由 'I' 同 'O' 組成嘅字串 $s$，請編寫程式，輸出字串 $s$ 入面有幾多處包含字串 $P_n$。

輸入格式

輸入共 $3$ 行： - 第 $1$ 行包含整數 $n$（$1 \le n \le 1000000$）。 - 第 $2$ 行包含整數 $m$（$1 \le m \le 1000000$），其中 $m$ 代表字串 $s$ 嘅字元數量。 - 第 $3$ 行包含字串 $s$，字串 $s$ 只由 'I' 同 'O' 組成。

所有測試數據均滿足 $2n + 1 \le m$。另外，喺佔總分 $50\%$ 嘅測試數據入面，滿足 $n \le 100$ 同埋 $m \le 10000$。

輸出格式

輸出得 $1$ 行，包含一個整數，代表字串 $s$ 入面有幾多處包含字串 $P_n$。如果字串 $s$ 入面完全唔包含 $P_n$，就輸出整數 $0$。

Sample 1

1
13
OOIOIOIOIIOII

4

Sample 2

2
13
OOIOIOIOIIOII

2

範例解釋

當整數 $n$ 係 $1$、字串 $s$ 係 OOIOIOIOIIOII 嗰陣，字串 $P_1$ 即係 IOI 如以下圖 1-2 所示包含喺 $4$ 處，所以要輸出嘅整數係 $4$。

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

圖 1-2：喺範例 1 入面，字串 $P_1$ 包含喺 $4$ 處

當整數 $n$ 係 $2$、字串 $s$ 係 OOIOIOIOIIOII 嗰陣，字串 $P_2$ 即係 IOIOI 如以下圖 1-3 所示包含喺 $2$ 處，所以要輸出嘅整數係 $2$。

OOIOIOIOIIOII
  ^^^^^
    ^^^^^

圖 1-3：喺範例 2 入面，字串 $P_2$ 包含喺 $2$ 處