题目描述

给定一串环形排列的鹅卵石。这串鹅卵石共有 $n$ 个，每个鹅卵石可能是黑色或者白色。

Mirko 要对这串鹅卵石进行 $k$ 次操作。这串鹅卵石为初始石串。一次操作的描述如下：

• 如果相邻的鹅卵石颜色相同，则把它们之间放入一个黑色鹅卵石；

• 如果相邻的鹅卵石颜色不同，则把它们之间再放入一个白色鹅卵石；

• 重复上述步骤 $k$ 次。

• 这里的相邻只计算原有的鹅卵石。后放入的不计。

• 最终，原来的一串鹅卵石将会增加到 $2\times n$ 个。把初始石串拿走，剩下的鹅卵石（也就是后加入的 $n$ 个）即为一次操作后的结果。

给定一个初始石串，经过 $k$ 次操作后会得到一个结果。你需要求出：有多少种不同的初始石串同样可以经过 $k$ 次操作得到同样的结果？

输入格式

输入第一行有两个整数 $n,k$。

第二行一行 $n$ 个字符，描述这串石头的颜色。W 表示白色，B 表示黑色。

输出格式

输出一行一个整数，表示不同的初始石串的种类数。（输入的那一种计入答案）

3 1
BBW

2

6 2
WBWWBW

3

提示

样例 1 解释

石串 BBW 和 WBW 在经过 $1$ 次操作后同样得到石串 BWW。故有 $2$ 种初始石串。

数据规模与约定

对于 $100\%$ 的数据，保证 $1\le n\le 100$，$1\le k\le 10$。

说明

题目译自 COCI2006-2007 Regional Competition T4 CIRCLE。