P6482 [CRCI2006-2007] CIRCLE

You are given a ring (circular arrangement) of pebbles. There are $n$ pebbles in total, and each pebble is either black or white. Mirko will perform $k$ operations on this ring of pebbles. This ring is called the **initial sequence**. One operation is defined as follows: - If two adjacent pebbles have the same color, insert a black pebble between them. - If two adjacent pebbles have different colors, insert a white pebble between them. - Repeat the above steps $k$ times. - **Here, adjacency is considered only among the original pebbles. The pebbles inserted later are not counted.** - In the end, the original ring of pebbles will increase to $2\times n$ pebbles. Remove the **initial sequence**; the remaining pebbles (i.e., the $n$ newly inserted pebbles) are the result after one operation. Given an initial sequence, after $k$ operations you will obtain a result. You need to find: how many different initial sequences can also produce the same result after $k$ operations?

The first line contains two integers $n,k$. The second line contains $n$ characters describing the colors of the pebbles. `W` means white, and `B` means black.

Output one integer in one line, representing the number of different initial sequences. (The given one in the input should be included in the answer.)

#### Sample 1 Explanation The sequences `BBW` and `WBW` both become `BWW` after $1$ operation. Therefore, there are $2$ possible initial sequences. #### Constraints For $100\%$ of the testdata, $1\le n\le 100$ and $1\le k\le 10$. #### Note **Translated from [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [Regional Competition](https://hsin.hr/coci/archive/2006_2007/regional_tasks.pdf) *T4 CIRCLE***。 Translated by ChatGPT 5