### 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.

### Output

Output the number of possible distinct starting circles on a single line.

### Sample Tests

## Input3 1 BBW ## Output2 |
## Input6 2 WBWWBW ## Output3 |

**Test case 1 clarification:** The circles BBW and WBW become circle BWW after one transformation.

All Submissions

Best Solutions

**Point Value:** 15

**Time Limit:** 1.00s

**Memory Limit:** 32M

**Added:** Jul 10, 2013

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...