題目描述

對於整數 $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$ 處