Với số nguyên \(n\ge 1\), gọi \(P_n\) là xâu gồm \(n+1\) chữ I và \(n\) chữ O, được xếp xen kẽ và bắt đầu bằng I. Cả I và O đều là chữ cái Latin in hoa. Chẳng hạn, \(P_1=\) IOI, \(P_2=\) IOIOI, \(P_3=\) IOIOIOI.

Cho số nguyên \(n\) và xâu \(s\) chỉ gồm các chữ I, O. Một lần xuất hiện của \(P_n\) trong \(s\) là một đoạn gồm các ký tự liên tiếp của \(s\) bằng \(P_n\). Các lần xuất hiện có thể chồng lấn nhau.

Yêu cầu

Đếm số vị trí xuất hiện của \(P_n\) trong \(s\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng thứ nhất chứa số nguyên \(n\).
• Dòng thứ hai chứa số nguyên \(m\), là độ dài của \(s\).
• Dòng thứ ba chứa xâu \(s\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên trên một dòng: số lần xuất hiện của \(P_n\) trong \(s\). Nếu không có lần xuất hiện nào, ghi \(0\).

Ràng buộc

• \(1\le n\le 1\,000\,000\).
• \(1\le m\le 1\,000\,000\).
• \(2n+1\le m\).
• Xâu \(s\) có đúng \(m\) ký tự và chỉ gồm I, O.
• Giới hạn thời gian: \(1\) giây.
• Giới hạn bộ nhớ: \(64\) MB.

Chấm điểm

Bài có \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm, tổng cộng \(20\) điểm.

• \(50\%\) số điểm (\(10\) điểm) ứng với các bộ dữ liệu thỏa mãn \(n\le 100\) và \(m\le 10\,000\).

Ví dụ

1
13
OOIOIOIOIIOII

4

Ở đây \(P_1=\) IOI. Bốn lần xuất hiện được gạch chân trong hình dưới đây.

2
13
OOIOIOIOIIOII

2

Ở đây \(P_2=\) IOIOI. Hai lần xuất hiện được gạch chân trong hình dưới đây.