한 줄 좌석의 단체 예약

문제

영화관의 한 상영관에는 일렬로 이어진 좌석 N개가 있다. 좌석에는 왼쪽부터 1번부터 N번까지 번호가 붙어 있다. 직원은 이 줄의 현재 예약 상태를 길이가 N인 문자열로 관리한다. 문자열의 왼쪽에서 i번째 문자는 i번 좌석의 상태를 나타낸다. 문자 O는 아직 예약되지 않은 좌석을 뜻하고, 문자 X는 이미 예약된 좌석을 뜻한다. 여기서 O는 숫자 0이 아니라 영어 대문자다. 함께 영화를 보려는 손님 K명이 방문했다. 손님들은 모두 같은 줄에서 서로 붙어 있는 좌석에 앉으려 한다. 따라서 시작 좌석 하나를 정하고 그 좌석부터 오른쪽으로 정확히 K개의 연속한 좌석을 선택해야 한다. 선택한 좌석이 모두 O일 때만 단체 예약이 가능하다. 선택한 구간에 X가 하나라도 있거나, 구간이 줄의 마지막 좌석을 넘어가면 예약할 수 없다. 줄의 마지막 좌석과 첫 좌석은 서로 이어져 있지 않다. 직원은 실제 예약을 진행하기 전에 가능한 선택이 몇 가지인지 알고 싶어 한다. 시작 좌석이 다르면 서로 다른 선택으로 센다. 두 선택에 같은 좌석이 포함되어 있어도 각각 가능한 선택이라면 둘 다 센다. 예를 들어 빈 좌석 세 개가 연속해 있고 K가 2라면, 그 구간의 앞 두 좌석을 고르는 방법과 뒤 두 좌석을 고르는 방법은 서로 다른 선택이다. 이 계산은 현재 예약 상태에서 가능한 선택을 모두 세는 작업이다. 한 선택을 셌다고 해서 좌석을 X로 바꾸지 않으며, 여러 단체가 동시에 앉을 수 있는지를 계산하지도 않는다. K가 1이면 빈 좌석 하나가 각각 한 가지 선택이 된다. 현재 상태 문자열과 손님의 수가 주어질 때 단체 예약이 가능한 선택의 개수를 구한다. 가능한 선택이 하나도 없으면 0을 출력한다.

입력

첫째 줄에 정수 N과 K가 공백으로 주어진다. 1 ≤ K ≤ N ≤ 1000이다.
둘째 줄에 길이가 N인 문자열 S가 주어진다. S는 영어 대문자 O와 X로만 이루어져 있으며 공백을 포함하지 않는다.

출력

단체 예약이 가능한 선택의 개수를 정수 하나로 출력한다. 가능한 선택이 없으면 0을 출력한다.

8 2
OOOXOOOO

5

4 3
OXOO

0

1 1
O

1

출처: Devin.KR 자체 제작