시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB76161017.857%

문제

어느 여름날 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의 변환 전 원이 주어진다.

출력

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

예제 입력 1

3 1
BBW

예제 출력 1

2

예제 입력 2

6 2
WBWWBW

예제 출력 2

3

힌트

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

W3sicHJvYmxlbV9pZCI6IjMwMjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2ZDBcdWQ2MTUgXHVjNzkwXHVhYzA4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWIyOTAgXHVjNWVjXHViOTg0XHViMGEwIE1pcmtvXHViMjk0IFx1YmMyOVx1YzVkMFx1YzExYyBcdWI4MDhcdWJhYThcdWIxMjRcdWM3NzRcdWI0ZGNcdWI5N2MgXHViOWM4XHVjMmRjXHVhY2UwIFx1Yzc4OFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+JnF1b3Q7XHVjNWVjISZxdW90OywgU3RhbmtvXHVhYzAwIFx1YzE4Y1x1YjlhY1x1Y2NlNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+JnF1b3Q7XHViMDljIFx1YWMwMFx1YjA1NCBcdWM2YjBcdWI5YWMgXHVjOTExIFx1YjIwNFx1YWMwMCBcdWIzNTQgXHViNmYwXHVjNWI0XHViMDljXHVjOWMwIFx1YWQ4MVx1YWUwOFx1ZDU3NC4gXHVjNWI0XHViNTRjPyZxdW90OywgTWlya29cdWFjMDAgXHViYjNjXHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD4mcXVvdDtcdWM3OTggXHViNGU0XHVjNWI0ISBcdWIwYjRcdWFjMDAgXHViNGI3XHViOWM4XHViMmY5XHVjNWQwIE5cdWFjMWNcdWM3NTggXHVjNzkwXHVhYzA4XHVjNzQ0IFx1YzZkMFx1ZDYxNVx1YzczY1x1Yjg1YyBcdWIxOTNcdWM1NThcdWM1YjQuIFx1YzViNFx1YjVhNCBcdWFjNzQgXHVhYzgwXHVjNzQwXHVjMGM5XHVjNzc0XHVhY2UwIFx1YzViNFx1YjVhNCBcdWFjNzQgXHVkNzcwXHVjMGM5XHVjNzc0XHVjOWMwLiBcdWIwOThcdWIyOTQgXHVjNzc0XHVjNmMzXHVkNTVjIFx1Yzc5MFx1YWMwOFx1Yzc1OCBcdWMwYzlcdWM3NzQgXHVhYzE5XHVjNzNjXHViYTc0IFx1YWRmOCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVhYzgwXHVjNzQwIFx1Yzc5MFx1YWMwOFx1Yzc0NCwgXHVjMGM5XHVjNzc0IFx1YjJlNFx1Yjk3NFx1YmE3NCBcdWQ3NzBcdWMwYzkgXHVjNzkwXHVhYzA4XHVjNzQ0IFx1YjEyM1x1Yzc0NCBcdWFjNzBcdWM1N2MuIFx1YWRmOFx1YjgwN1x1YWM4YyBcdWI0MThcdWJhNzQgMk5cdWFjMWNcdWM3NTggXHVjNzkwXHVhYzA4XHVjNzc0IFx1YzZkMFx1ZDYxNVx1Yzc0NCBcdWM3NzRcdWI4ZThcdWFjZTAgXHVjNzg4XHVhY2EwXHVjOWMwLiBcdWIwOWMgXHVhZTMwXHVjODc0XHVjNzU4IE5cdWFjMWNcdWI5N2MgXHVjNWM2XHVjNTY4IFx1YWM3MFx1YWNlMCwgXHVhZGY4XHViN2VjXHViYTc0IFx1YzBjOFx1Yjg1YyBcdWNkOTRcdWFjMDBcdWI0MWMgTlx1YWMxY1x1YjljYyBcdWIwYThcdWM3NDQgXHVhYzcwXHVjNTdjLiBcdWIwOWMgXHVjNzc0XHVhYzc4IFx1YzgxNVx1ZDY1NVx1ZDc4OCBLXHViYzg4IFx1ZDU2MCBcdWFjNzBcdWFjZTAsIFx1YjEwYyBcdWI5ZTggXHVjYzk4XHVjNzRjIFx1Yzc4OFx1YjM1OCBcdWM3OTBcdWFjMDhcdWM3NDQgXHViOWRlXHVjZDk0XHViYTc0IFx1YjNmYy4mcXVvdDssIFN0YW5rb1x1YWMwMCBcdWM3YTVcdWQ2NjlcdWQ1NThcdWFjOGMgXHViOWQwXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD4mcXVvdDtcdWQ1YzghIFx1YjA5YyBcdWIxMjQgXHVjMThkXHVjNzg0XHVjMjE4XHVjNWQwIFx1YjE4MFx1YzU0NFx1YjA5OFx1YzljMCBcdWM1NGFcdWM3NDQgXHVhYzcwXHVjNTdjISBcdWNjOThcdWM3NGMgXHVjNzg4XHViMzU4IFx1Yzc5MFx1YWMwOFx1Yzc0NCBcdWI5ZGVcdWNkOTRcdWIyOTQgXHVhYzc0IFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YzljMFx1YjljYywgS1x1YmM4OCBcdWJjYzBcdWQ2NThcdWM3NDQgXHVkMWI1XHVkNTc0IFx1YjEyNCBcdWFjODNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWIwYjRcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1YjI5NCBcdWFkNmNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzljMC4mcXVvdDssIE1pcmtvXHVhYzAwIFx1YjlkMFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+U3RhbmtvXHVhYzAwIFx1YzcwNFx1YzVkMFx1YzExYyBcdWMxMjRcdWJhODVcdWQ1NWMgS1x1YmM4OFx1Yzc1OCBcdWJjYzBcdWQ2NThcdWM3NDQgXHVkNTU4XHVhZTMwIFx1YzgwNFx1Yzc1OCBcdWM2ZDBcdWM3NTggXHVhZDZjXHVjMTMxXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIEtcdWJjODhcdWM3NTggXHViY2MwXHVkNjU4IFx1ZDZjNFx1YzVkMCBTdGFua29cdWM3NTggXHVjNmQwXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFjYjBcdWFjZmNcdWI5N2MgXHViMGI0XHViMjk0IFx1YzZkMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjMTM4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWI3N2MuPFwvcD5cclxuXHJcbjxwPlx1ZDY4Y1x1YzgwNFx1YzJkY1x1Y2YxY1x1YzExYyBcdWFjMTlcdWM1NDRcdWM5YzBcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YWMxOVx1Yzc0MCBcdWM2ZDBcdWM3M2NcdWI4NWMgXHVjZGU4XHVhZTA5XHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IEJCV1x1YzY0MCBCV0JcdWIyOTQgXHVhYzE5XHVjOWMwXHViOWNjLCBCQldXQldcdWM2NDAgV1dCQldCXHViMjk0IFx1YjJlNFx1Yjk3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCBOXHVhY2ZjIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMyAmbGU7IE4gJmxlOyAxMDAsIDEgJmxlOyBLICZsZTsgMTApPFwvcD5cclxuXHJcbjxwPk5cdWM3NDAgXHVjNzkwXHVhYzA4XHVjNzU4IFx1YzIxOCwgS1x1YjI5NCBTdGFua29cdWFjMDAgXHViOWNjXHViNGUwIFx1YmNjMFx1ZDY1OFx1Yzc1OCBcdWQ2OWZcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YWMxY1x1Yzc1OCAmIzM5O0ImIzM5O1x1YzY0MCAmIzM5O1cmIzM5O1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgU3RhbmtvXHVjNzU4IFx1YmNjMFx1ZDY1OCBcdWM4MDQgXHVjNmQwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQ1NWMgXHVjOTA0XHViODVjIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+QkJXXHVjNjQwIFdCV1x1YjI5NCBcdWQ1NWMgXHViYzg4XHVjNzU4IFx1YmNjMFx1ZDY1OCBcdWQ2YzRcdWM1ZDAgQldXXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMwMjEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDSVJDTEUiLCJkZXNjcmlwdGlvbiI6IjxwPk9uZSBuaWNlIHN1bW1lciBkYXkgd2hpbGUgTWlya28gd2FzIGRyaW5raW5nIGxlbW9uYWRlIGluIGhpcyByb29tLi4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZxdW90O0JpZyBicm90aGVyISZxdW90OywgeWVsbHMgU3RhbmtvLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mcXVvdDtJIHdvbmRlciBzb21ldGltZXMgd2hpY2ggb2YgdGhlIHR3byBvZiB1cyBpcyB0aGUgYmlnIG9uZS4gV2hhdCBpcyBpdD8mcXVvdDssIE1pcmtvIGFza2VkLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mcXVvdDtMaXN0ZW4gY2FyZWZ1bGx5ISBJbiB0aGUgYmFja3lhcmQgSSBoYXZlIE4gcGViYmxlcyBhcnJhbmdlZCBpbiBhIGNpcmNsZS4gU29tZSBvZiB0aGUgcGViYmxlcyBhcmUgYmxhY2ssIHNvbWUgYXJlIHdoaXRlLiBJIHdpbGwgZG8gdGhlIGZvbGxvd2luZzogYmV0d2VlbiBhbnkgdHdvIG5laWdoYm91cmluZyBwZWJibGVzIG9mIHRoZSBzYW1lIGNvbG91ciBJIHdpbGwgaW5zZXJ0IGEgYmxhY2sgcGViYmxlLCBhbmQgYmV0d2VlbiBhbnkgdHdvIG5laWdoYm91cmluZyBwZWJibGVzIG9mIGRpZmZlcmVudCBjb2xvdXJzIEkgd2lsbCBpbnNlcnQgYSB3aGl0ZSBwZWJibGUuIEF0IHRoYXQgcG9pbnQgdGhlcmUgd2lsbCBiZSAyTiBwZWJibGVzIGluIHRoZSBjaXJjbGUsIHNvIEkgd2lsbCByZW1vdmUgdGhlIHN0YXJ0aW5nIE4gcGViYmxlcyBzbyB0aGF0IG9ubHkgdGhlIG5ld2x5IGFkZGVkIE4gcGViYmxlcyByZW1haW4uIEFuZCBhbGwgdGhpcyBJIGludGVuZCB0byBkbyBleGFjdGx5IEsgdGltZXMuIEFuZCB0aGVuIHlvdSBhcmUgdG8gZGV0ZXJtaW5lIG15IHN0YXJ0aW5nIGNpcmNsZS4mcXVvdDssIHNhaWQgU3RhbmtvIGxvbmctd2luZGVkbHkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZxdW90O0hhISBJIHNoYWxsIG5vdCBmYWxsIHByZXkgdG8geW91ciB0cmlja2VyeSEgSSBjYW4gc2VlIHRoYXQgaXQgaXMgbm90IG5lY2Vzc2FyaWx5IHBvc3NpYmxlIHRvIGtub3cgZXhhY3RseSB3aGF0IHRoZSBzdGFydGluZyBjaXJjbGUgd2FzLCBidXQgSSBjYW4gY291bnQgdGhlIG51bWJlciBvZiBkaXN0aW5jdCBzdGFydGluZyBjaXJjbGVzIHRoYXQgZ2l2ZSB0aGUgc2FtZSByZXN1bHQgYXMgeW91ciBjaXJjbGUgYWZ0ZXIgZXhhY3RseSBLIG9mIHRob3NlIHdlaXJkIHRyYW5zZm9ybWF0aW9ucyBvZiB5b3VycyZxdW90OywgYW5zd2VyZWQgTWlya28uJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gdGhlIGNvbmZpZ3VyYXRpb24gb2YgdGhlIGNpcmNsZSBiZWZvcmUgU3RhbmtvIHBlcmZvcm1lZCB0aGUgdHJhbnNmb3JtYXRpb24gZGVzY3JpYmVkIGFib3ZlIEsgdGltZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGRldGVybWluZXMgdGhlIG51bWJlciBvZiBkaXN0aW5jdCBzdGFydGluZyBjaXJjbGVzIHRoYXQgZ2l2ZSB0aGUgc2FtZSBjaXJjbGUgYWZ0ZXIgSyB0cmFuc2Zvcm1hdGlvbnMgYXMgU3RhbmtvJiMzOTtzIG9yaWdpbmFsIGNpcmNsZSBkb2VzIGFmdGVyIEsgdHJhbnNmb3JtYXRpb25zLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ud28gY29uZmlndXJhdGlvbnMgb2YgcGViYmxlcyBhcmUgY29uc2lkZXJlZCB0byBiZSB0aGUgc2FtZSBjaXJjbGUgaWYgb25lIGNhbiBiZSBnb3R0ZW4gZnJvbSB0aGUgb3RoZXIgYnkgcm90YXRpbmcgaXQgYW55IG51bWJlciBvZiBwb3NpdGlvbnMuIEZvciBleGFtcGxlIEJCVyBhbmQgQldCIGlzIHRoZSBzYW1lIGNpcmNsZSB3aGVyZWFzIEJCV1dCVyBhbmQgV1dCQldCIGFyZSBub3QuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgSywgMyAmbGU7IE4gJmxlOyAxMDAsIDEgJmxlOyBLICZsZTsgMTAsIHdoZXJlIE4gaXMgdGhlIG51bWJlciBvZiBwZWJibGVzIGluIHRoZSBjaXJjbGUgYW5kIEsgaXMgdGhlIG51bWJlciBvZiB0cmFuc2Zvcm1hdGlvbnMgbWFkZSBieSBTdGFua28uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBleGFjdGx5IE4gY2hhcmFjdGVycyAmIzM5O0ImIzM5OyBvciAmIzM5O1cmIzM5OyByZXByZXNlbnRpbmcgU3RhbmtvJiMzOTtzIG9yaWdpbmFsIGNpcmNsZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG51bWJlciBvZiBwb3NzaWJsZSBkaXN0aW5jdCBzdGFydGluZyBjaXJjbGVzIG9uIGEgc2luZ2xlIGxpbmUuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBjaXJjbGVzIEJCVyBhbmQgV0JXIGJlY29tZSBjaXJjbGUgQldXIGFmdGVyIG9uZSB0cmFuc2Zvcm1hdGlvbi48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=