非常简单数位 dp。
先差分转成前缀询问，然后记录状态 \(dp_{p, num, hv, pre}\) 表示当前考虑到第 \(p\) 位，还剩 \(num\) 次改变定义的机会，\(hv\) 表示这一位是否考虑大小限制，\(pre\) 表示上一位的定义是否和现实左右一样。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1010, MOD = 1e9 + 7;
inline void inc(int &x, int y) { x += y, x >= MOD && (x -= MOD); }
inline void dec(int &x, int y) { x -= y, x < 0 && (x += MOD); }
inline int add(int x, int y) { return x += y, x >= MOD ? x - MOD : x; }
inline int sub(int x, int y) { return x -= y, x < 0 ? x + MOD : x; }
int n, k, pw2[MAXN];
bool dir[MAXN], lmt[MAXN];
char s1[MAXN], s2[MAXN];
pair<int, int> dp[MAXN][MAXN][2][2];
pair<int, int> dfs(int p, int num, bool hv, bool pre) {
if (p == n + 1) return {!num, 0};
if (dp[p][num][hv][pre].first != -1) return dp[p][num][hv][pre];
int ret1 = 0, ret2 = 0, up = (hv ? lmt[p] : 1);
for (int i = 0; i <= up; ++i) {
bool cst = ((i != dir[p]) != pre);
if (cst && !num) continue;
auto tmp = dfs(p + 1, num - cst, hv && i == up, i != dir[p]);
inc(ret1, tmp.first);
inc(ret2, tmp.second);
if (i) ret2 = (ret2 + (ll)tmp.first * pw2[n - p]) % MOD;
}
return dp[p][num][hv][pre] = {ret1, ret2};
}
int solve(char s[]) {
for (int i = 1; i <= n; ++i) lmt[i] = s[i] - '0';
for (int p = 1; p <= n; ++p) {
for (int num = 0; num <= k; ++num) {
for (int hv = 0; hv < 2; ++hv) {
for (int pre = 0; pre < 2; ++pre)
dp[p][num][hv][pre].first = -1;
}
}
}
auto t1 = dfs(2, k, 1, 0), t2 = dfs(2, k, 1, 1);
return ((ll)(t1.first + t2.first) * pw2[n - 1] + t1.second + t2.second) % MOD;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
pw2[0] = 1;
for (int i = 1; i <= n; ++i) pw2[i] = add(pw2[i - 1], pw2[i - 1]);
for (int i = 2; i <= n; ++i) {
char ch;
cin >> ch;
dir[i] = (ch == 'R');
}
cin >> (s1 + 1) >> (s2 + 1);
--s1[n];
for (int i = n; s1[i] < '0'; --i) s1[i] = '1', --s1[i - 1];
if (s1[1] == '0') {
cout << solve(s2) << "\n";
} else {
cout << sub(solve(s2), solve(s1)) << "\n";
}
return 0;
}