PEG Judge - COCI06 Regional

COCI 2006/2007, Croatian Regional

Task CIRCLE

One nice summer day while Mirko was drinking lemonade in his room...

"Big brother!", yells Stanko.

"I wonder sometimes which of the two of us is the big one. What is it?", Mirko asked.

"Listen carefully! In the backyard I have N pebbles arranged in a circle. Some of the pebbles are black, some are white. I will do the following: between any two neighbouring pebbles of the same colour I will insert a black pebble, and between any two neighbouring pebbles of different colours I will insert a white pebble. At that point there will be 2N pebbles in the circle, so I will remove the starting N pebbles so that only the newly added N pebbles remain. And all this I intend to do exactly K times. And then you are to determine my starting circle.", said Stanko long-windedly.

"Ha! I shall not fall prey to your trickery! I can see that it is not necessarily possible to know exactly what the starting circle was, but I can count the number of distinct starting circles that give the same result as your circle after exactly K of those weird transformations of yours", answered Mirko.

You are given the configuration of the circle before Stanko performed the transformation described above K times.

Write a program that determines the number of distinct starting circles that give the same circle after K transformations as Stanko's original circle does after K transformations.

Two configurations of pebbles are considered to be the same circle if one can be gotten from the other by rotating it any number of positions. For example BBW and BWB is the same circle whereas BBWWBW and WWBBWB are not.

Input

The first line of input contains two integers N and K, 3 ≤ N ≤ 100, 1 ≤ K ≤ 10, where N is the number of pebbles in the circle and K is the number of transformations made by Stanko.

The second line contains exactly N characters 'B' or 'W' representing Stanko's original circle.