看起来很不可做的样子，但是要求任意位置都存在合法操作序列，看起来限制挺强的，我们尝试把这个限制转化为容易搞的条件。
一种颜色
如果 (S) 只有一种颜色，那么我们只要要求另一种颜色不连续即可（因为只要每个点都有一个相邻的 (S) 中的那个颜色，那么就可以借此反复横跳）于是答案为
当然如果 (n = 1)，即使另一种颜色不相邻也不行，需要特判一下。
两种颜色
现在我们考虑更普遍的情况。假设第一种颜色为 (R)。那么我们有如下要求：
不存在相邻的 B
显然，如果存在相邻的 B，那么中间的那个点就不合法了。
于是我们可以将环看做若干形如 RRR...RRB 的“段”。
每段的长均为偶数（R连续段均为奇数)
这个主要是为了应对 S 中的第一段 R 后面的那个 B。我们需要在前面的那些 R 以后一种到 B 的旁边，如果存在一 R 连续段 的长为偶数，那么最终的奇偶性就肯定不对了。手玩一下就好了。
段长不超最短奇R段长
定义“最短奇R段”表示 S 中长为奇数且最短的 R 连续段，那么我们要求每个段长不超过最短奇R段长。
对于 B 连续段，我们可以在 B 的旁边反复横跳。
对于 R 连续段，我们需要在 R 的旁边反复横跳，但是要求最终要跳到 B 的旁边。如果此 R 连续段长度为偶数，那么直接在挨着 B 的那个 R 旁边反复横跳即可；如果为奇数，我们就需要调到 R 连续段的另一头，于是要求此 R 连续段不能太长。
当然，如果这一段是最后一段，则没有这一要求。
段长不超起始R段长
我们要保证一开始点要有足够的时间跳到 B 的旁边，因此需要对段长进行限制。由于每一 R 连续段长度均为奇数，极限数据并不在段的中间，而在段的一边。
仔细思考，发现这三个要求已经足够了。于是直接将题意转化成：
将长为 (n) 的环划分成若干段，每一段的长度不能超过 (k)，且只能在奇数处划分，的方案数。
于是直接大力 DP 即可。然而环上 DP 毕竟还是有些困难，我们枚举 (1) 号点的右边的那个边所在的“段”的长度 (i)，答案为 (sum_{i}i imes f_i)。其中 (f_i) 表示序列上将长为 (i) 的序列分段的方案数。这个就是经典的 DP 问题了。
(Code:)
namespace jzp1 {
ll jie[N], jieni[N];
inline ll get_c(int n, int m)
inline ll quickpow(ll x, int k)
inline void sol() {
if (n == 1) { puts("1"); return ; }
jie[0] = jieni[0] = 1;
int up = n + 1;
for (int i = 1; i <= up; ++i) jie[i] = jie[i - 1] * i % P;
jieni[up] = quickpow(jie[up], P - 2);
for (int i = up - 1; i; --i) jieni[i] = jieni[i + 1] * (i + 1) % P;
ll res = 0;
for (int i = 0; i <= n; ++i) {
res = (res + get_c(n - i + 1, i) - get_c(n - i - 1, i - 2)) % P;
}
printf("%lld
", (res % P + P) % P);
}
}
ll f[N];
ll sum[N];
int main() {
read(n), read(m);
scanf("%s", s + 1);
bool flag = false;
int tmp = 0;
for (int i = 1; i <= m; ++i) if (s[i] != s[1]) { flag = true; tmp = i - 1; break; }
if (!flag) { jzp1::sol(); return 0; }
if (n & 1) { puts("0"); return 0; }
int lst = 1, mn = tmp | 1;
for (int i = 2; i <= m; ++i) {
if (s[i] != s[1]) {
if (lst & 1) MIN(mn, lst);
lst = 0;
continue;
}
if (s[i] == s[i - 1]) ++lst;
else {
if (lst & 1) MIN(mn, lst);
lst = 1;
}
}
n >>= 1;
int k = (mn + 1) >> 1;
MIN(k, n);
f[0] = 1; sum[0] = 1;
for (int i = 1; i <= n; ++i) {
if (i <= k) f[i] = sum[i - 1];
else f[i] = (sum[i - 1] - sum[i - k - 1]) % P;
sum[i] = (sum[i - 1] + f[i]) % P;
}
ll ans = 0;
for (int i = 1; i <= k; ++i) {
ans = (ans + f[n - i] * i) % P;
}
ans = (ans << 1) % P;
printf("%lld
", (ans % P + P) % P);
return 0;
}