Verkefni

Fyrir heiltölu $n$ ($1 \le n$) kallast strengurinn sem myndast með því að raða til skiptis $n+1$ bókstöfum 'I' og $n$ bókstöfum 'O', byrjað á 'I', $P_n$. Hér eru 'I' og 'O' hástafir í enska stafrófinu.

• $P_1$: IOI
• $P_2$: IOIOI
• $P_3$: IOIOIOI
• $P_n$: IOIOIO $\cdots$ OI ($n$ stykki af 'O')

Mynd 1-1: Strengurinn $P_n$ fyrir heiltölu $n$ ($1 \le n$)

Gefin er heiltala $n$ og strengur $s$ sem samanstendur eingöngu af 'I' og 'O'. Skrifið forrit sem prentar út á hve mörgum stöðum í strengnum $s$ strengurinn $P_n$ kemur fyrir.

Inntak

Inntakið samanstendur af $3$ línum: - Á $1$. línu er heiltala $n$ ($1 \le n \le 1000000$). - Á $2$. línu er heiltala $m$ ($1 \le m \le 1000000$), þar sem $m$ táknar fjölda stafa í strengnum $s$. - Á $3$. línu er strengurinn $s$, sem samanstendur eingöngu af 'I' og 'O'.

Í öllum prófunargögnum gildir $2n + 1 \le m$. Að auki gildir fyrir $50\%$ stiga að $n \le 100$ og $m \le 10000$.

Úttak

Prentið út $1$ línu sem inniheldur eingöngu heiltölu sem segir til um á hve mörgum stöðum í strengnum $s$ strengurinn $P_n$ kemur fyrir. Ef $P_n$ kemur hvergi fyrir í $s$, prentið þá heiltöluna $0$.

Sample 1

1
13
OOIOIOIOIIOII

4

Sample 2

2
13
OOIOIOIOIIOII

2

Skýring á dæmum

Þegar heiltalan $n$ er $1$ og strengurinn $s$ er OOIOIOIOIIOII, kemur strengurinn $P_1$, þ.e. IOI, fyrir á $4$ stöðum eins og sýnt er á Mynd 1-2 hér að neðan, þannig að heiltalan sem á að prenta út er $4$.

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

Mynd 1-2: Í Dæmi 1 kemur strengurinn $P_1$ fyrir á $4$ stöðum

Þegar heiltalan $n$ er $2$ og strengurinn $s$ er OOIOIOIOIIOII, kemur strengurinn $P_2$, þ.e. IOIOI, fyrir á $2$ stöðum eins og sýnt er á Mynd 1-3 hér að neðan, þannig að heiltalan sem á að prenta út er $2$.

OOIOIOIOIIOII
  ^^^^^
    ^^^^^

Mynd 1-3: Í Dæmi 2 kemur strengurinn $P_2$ fyrir á $2$ stöðum