시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 63 10 7 14.583%

문제

어느 여름날 Mirko는 방에서 레모네이드를 마시고 있었다.

"여!", Stanko가 소리쳤다.

"난 가끔 우리 중 누가 더 뛰어난지 궁금해. 어때?", Mirko가 물었다.

"잘 들어! 내가 뒷마당에 N개의 자갈을 원형으로 놓았어. 어떤 건 검은색이고 어떤 건 흰색이지. 나는 이웃한 자갈의 색이 같으면 그 사이에 검은 자갈을, 색이 다르면 흰색 자갈을 넣을 거야. 그렇게 되면 2N개의 자갈이 원형을 이루고 있겠지. 난 기존의 N개를 없앨 거고, 그러면 새로 추가된 N개만 남을 거야. 난 이걸 정확히 K번 할 거고, 넌 맨 처음 있던 자갈을 맞추면 돼.", Stanko가 장황하게 말했다.

"허! 난 네 속임수에 놀아나지 않을 거야! 처음 있던 자갈을 맞추는 건 불가능하지만, K번 변환을 통해 네 것과 같은 결과를 내는 경우의 수는 구할 수 있지.", Mirko가 말했다.

Stanko가 위에서 설명한 K번의 변환을 하기 전의 원의 구성이 주어졌을 때, K번의 변환 후에 Stanko의 원과 같은 결과를 내는 원의 수를 세는 프로그램을 작성하라.

회전시켜서 같아지는 경우는 같은 원으로 취급한다. 예를 들어 BBW와 BWB는 같지만, BBWWBW와 WWBBWB는 다르다.

입력

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

N은 자갈의 수, K는 Stanko가 만든 변환의 횟수이다.

둘째 줄에는 N개의 'B'와 'W'로 이루어진 Stanko의 변환 전 원이 주어진다.

출력

한 줄로 가능한 경우의 수를 출력한다.

예제 입력

3 1
BBW

예제 출력

2

힌트

BBW와 WBW는 한 번의 변환 후에 BWW가 된다.