Есептің шарты

Бүтін $n$ ($1 \le n$) саны үшін 'I' әрпінен бастап $n+1$ дана 'I' мен $n$ дана 'O' әріптерін кезектестіріп орналастыру арқылы алынатын жолды $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$-ші жолда тек 'I' мен 'O' таңбаларынан тұратын $s$ жолы жазылған.

Барлық тест деректерінде $2n + 1 \le m$ шарты орындалады. Сонымен қатар, ұпайдың $50\%$ бөлігінде $n \le 100$ және $m \le 10000$ шарты орындалады.

Шығыс деректер

$s$ жолының ішінде $P_n$ жолы неше жерде кездесетінін білдіретін бүтін сан ғана бар $1$ жолды шығарыңыз. Егер $P_n$ жолы $s$ ішінде мүлде кездеспесе, $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$ жерде кездеседі