Problem Description

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?

Input Format

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 Format

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

3 1
BBW

2

6 2
WBWWBW

3

Hint

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 Regional Competition T4 CIRCLE。

Translated by ChatGPT 5