Условие задачи

Для целого числа $n$ ($1 \le n$) назовём строкой $P_n$ строку, образованную чередованием $n+1$ букв 'I' и $n$ букв 'O', начиная с 'I'. Здесь 'I' и 'O' — заглавные буквы английского алфавита.

• $P_1$: IOI
• $P_2$: IOIOI
• $P_3$: IOIOIOI
• $P_n$: IOIOIO $\cdots$ OI ($n$ букв 'O')

Рисунок 1-1: Строка $P_n$ для целого числа $n$ ($1 \le n$)

Даны целое число $n$ и строка $s$, состоящая только из символов 'I' и 'O'. Напишите программу, которая выводит, в скольких местах строки $s$ содержится подстрока $P_n$.

Входные данные

Входные данные состоят из $3$ строк: - В $1$-й строке записано целое число $n$ ($1 \le n \le 1000000$). - Во $2$-й строке записано целое число $m$ ($1 \le m \le 1000000$), где $m$ обозначает количество символов в строке $s$. - В $3$-й строке записана строка $s$, состоящая только из символов 'I' и 'O'.

Во всех тестовых данных выполняется $2n + 1 \le m$. Кроме того, для $50\%$ баллов выполняется $n \le 100$ и $m \le 10000$.

Выходные данные

Выведите $1$ строку, содержащую только одно целое число — количество мест в строке $s$, где содержится строка $P_n$. Если строка $P_n$ не содержится в $s$, выведите целое число $0$.

Sample 1

1
13
OOIOIOIOIIOII

4

Sample 2

2
13
OOIOIOIOIIOII

2

Пояснение к примерам

Когда целое число $n$ равно $1$, а строка $s$ равна OOIOIOIOIIOII, строка $P_1$, то есть IOI, содержится в $4$ местах, как показано на Рисунке 1-2 ниже, поэтому нужно вывести целое число $4$.

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

Рисунок 1-2: В Примере 1 строка $P_1$ содержится в $4$ местах

Когда целое число $n$ равно $2$, а строка $s$ равна OOIOIOIOIIOII, строка $P_2$, то есть IOIOI, содержится в $2$ местах, как показано на Рисунке 1-3 ниже, поэтому нужно вывести целое число $2$.

OOIOIOIOIIOII
  ^^^^^
    ^^^^^

Рисунок 1-3: В Примере 2 строка $P_2$ содержится в $2$ местах