Умова задачі

Для цілого числа $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$ місцях