Aufgabenstellung

Für eine ganze Zahl $n$ ($1 \le n$) bezeichnen wir die Zeichenkette, die durch abwechselndes Aneinanderreihen von $n+1$ Buchstaben 'I' und $n$ Buchstaben 'O' (beginnend mit 'I') entsteht, als $P_n$. Hierbei sind 'I' und 'O' englische Großbuchstaben.

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

Abbildung 1-1: Die Zeichenkette $P_n$ für eine ganze Zahl $n$ ($1 \le n$)

Gegeben sind eine ganze Zahl $n$ und eine nur aus 'I' und 'O' bestehende Zeichenkette $s$. Schreiben Sie ein Programm, das ausgibt, an wie vielen Stellen in der Zeichenkette $s$ die Zeichenkette $P_n$ enthalten ist.

Eingabe

Die Eingabe besteht aus $3$ Zeilen: - In der $1$. Zeile steht eine ganze Zahl $n$ ($1 \le n \le 1000000$). - In der $2$. Zeile steht eine ganze Zahl $m$ ($1 \le m \le 1000000$). $m$ gibt die Anzahl der Zeichen der Zeichenkette $s$ an. - In der $3$. Zeile steht die Zeichenkette $s$, die nur aus 'I' und 'O' besteht.

Für alle Testdaten gilt $2n + 1 \le m$. Außerdem gilt für $50\%$ der Punkte $n \le 100$ und $m \le 10000$.

Ausgabe

Geben Sie $1$ Zeile aus, die nur eine ganze Zahl enthält: die Anzahl der Stellen, an denen die Zeichenkette $P_n$ in der Zeichenkette $s$ enthalten ist. Falls $P_n$ nicht in $s$ enthalten ist, geben Sie die ganze Zahl $0$ aus.

Sample 1

1
13
OOIOIOIOIIOII

4

Sample 2

2
13
OOIOIOIOIIOII

2

Erläuterung der Beispiele

Wenn die ganze Zahl $n$ gleich $1$ ist und die Zeichenkette $s$ gleich OOIOIOIOIIOII ist, ist die Zeichenkette $P_1$, also IOI, wie in Abbildung 1-2 unten gezeigt an $4$ Stellen enthalten; die auszugebende ganze Zahl ist daher $4$.

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

Abbildung 1-2: Im Fall von Beispiel 1 ist die Zeichenkette $P_1$ an $4$ Stellen enthalten

Wenn die ganze Zahl $n$ gleich $2$ ist und die Zeichenkette $s$ gleich OOIOIOIOIIOII ist, ist die Zeichenkette $P_2$, also IOIOI, wie in Abbildung 1-3 unten gezeigt an $2$ Stellen enthalten; die auszugebende ganze Zahl ist daher $2$.

OOIOIOIOIIOII
  ^^^^^
    ^^^^^

Abbildung 1-3: Im Fall von Beispiel 2 ist die Zeichenkette $P_2$ an $2$ Stellen enthalten