원형 자갈

N개의 자갈이 원형으로 놓여 있다. 각 자갈의 색은 검은색 B 또는 흰색 W이다.

한 번의 변환은 다음과 같이 이루어진다. 현재 원에서 서로 이웃한 두 자갈마다 새 자갈 하나를 놓는다. 마지막 자갈과 첫 번째 자갈도 이웃한 것으로 본다. 두 자갈의 색이 같으면 검은 자갈을, 다르면 흰 자갈을 놓는다. 그런 다음 기존 N개의 자갈을 모두 제거하고, 새로 놓인 N개의 자갈만 원형으로 남긴다.

입력으로 주어진 원은 K번의 변환을 하기 전의 초기 원 중 하나이다. 이 원을 정확히 K번 변환해 얻는 최종 원을 목표로 하자. 길이가 N인 초기 원 중에서 정확히 K번 변환했을 때 목표 최종 원과 같은 원이 되는 경우의 수를 구해야 한다.

회전해서 같아지는 원은 같은 원으로 취급한다. 예를 들어 BBW와 BWB는 같은 원이지만, BBWWBW와 WWBBWB는 다른 원이다.

첫째 줄에 두 정수 N과 K가 주어진다. (3 <= N <= 100, 1 <= K <= 10)

N은 자갈의 수이고, K는 변환 횟수이다.

둘째 줄에는 B와 W로만 이루어진 길이 N의 문자열이 주어진다. 이 문자열은 주어진 초기 원을 나타낸다.

가능한 초기 원의 개수를 한 줄에 출력한다.

BBW와 WBW는 한 번 변환하면 회전을 제외하고 같은 원이 된다.