题目描述

对于整数 $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$ 处