IOIOI

Interview

Time limit1sMemory limit256 MB

Summary

Count the occurrences of the alternating string P_N (N+1 I's and N O's) as a substring of S, counting overlaps.

Level: Medium5 of 10
Topics: String, Sliding window, Implementation, String matching
Solved: No attempts yet

Problem

Let $P_N$ be the string formed from $N+1$ copies of I and $N$ copies of O in which I and O alternate. That is, $P_N$ starts and ends with I, with $N$ Os in between.

$P_1$ = IOI
$P_2$ = IOIOI
$P_3$ = IOIOIOI
$P_N$ = IOIOI…OI (with $N$ Os)

Given a string $S$ consisting only of I and O and an integer $N$ , write a program that counts how many times $P_N$ occurs in $S$ . Overlapping occurrences are counted separately.

Input

The first line contains the integer $N$ .

The second line contains $M$ , the length of the string $S$ .

The third line contains the string $S$ .

Output

Print, on a single line, how many times $P_N$ occurs in $S$ .

Constraints

$1 \le N \le 1{,}000{,}000$
$2N+1 \le M \le 1{,}000{,}000$
$S$ consists only of I and O.

Examples2

Example 1
Input
```
1
13
OOIOIOIOIIOII
```
Expected output
```
4
```
Example 2
Input
```
2
13
OOIOIOIOIIOII
```
Expected output
```
2
```