#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
#define sz(x) ll(x.size())
#define base 1000000
#define M ll(1e9+7)
#define N 100005
#define F first
#define S second
#define pb push_back
#define in insert
#define eb emplace_back
#define ed "\n"
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef short int si;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
ll dp[1005][1005][2][2][2], kol[1005][1005][2][2][2];
bool mk[1005][1005][2][2][2];
void dob(ll &x, ll y) {x += y; x %= M;}
ll fx(ll x, ll y) {return (x * y) % M;}
ll sm(ll x, ll y) {return (x + y) % M;}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, k;
cin >> n >> k;
string s;
cin >> s;
for (int i = 0; i < sz(s); i++) if (s[i] == 'L') s[i] = '0'; else s[i] = '1';
string l, r;
cin >> l >> r;
mk[0][0][1][1][0] = mk[0][0][1][1][1] = 1;
kol[0][0][1][1][0] = kol[0][0][1][1][1] = dp[0][0][1][1][0] = dp[0][0][1][1][1] = 1;
n--;
for (int i = 0; i < n; i++)
for (int j = 0; j <= k; j++)
for (int fl = 0; fl < 2; fl++)
for (int fr = 0; fr < 2; fr++)
for (int t = 0; t < 2; t++)
{
if (!mk[i][j][fl][fr][t]) continue;
ll val = dp[i][j][fl][fr][t], koler = kol[i][j][fl][fr][t];
if (t == 0)
{
if (fl && fr)
{
if (s[i] == '1')
{
if (r[i + 1] != '0')
{
int nfl = fl;
if (l[i + 1] == '0') nfl = 0;
dob(dp[i + 1][j][nfl][fr][t], sm(koler, fx(2, val)));
mk[i + 1][j][nfl][fr][t] = 1;
dob(kol[i + 1][j][nfl][fr][t], koler);
}
}
else
{
if (l[i + 1] != '1')
{
int nfr = fr;
if (r[i + 1] == '1') nfr = 0;
dob(dp[i + 1][j][fl][nfr][t], fx(2, val));
mk[i + 1][j][fl][nfr][t] = 1;
dob(kol[i + 1][j][fl][nfr][t], koler);
}
}
if (j != k)
{
if (s[i] == '0')
{
if (r[i + 1] != '0')
{
int nfl = fl;
if (l[i + 1] == '0') nfl = 0;
dob(dp[i + 1][j + 1][nfl][fr][1], sm(koler, fx(2, val)));
mk[i + 1][j + 1][nfl][fr][1] = 1;
dob(kol[i + 1][j + 1][nfl][fr][1], koler);
}
}
else
{
if (l[i + 1] != '1')
{
int nfr = fr;
if (r[i + 1] == '1') nfr = 0;
dob(dp[i + 1][j + 1][fl][nfr][1], fx(2, val));
mk[i + 1][j + 1][fl][nfr][1] = 1;
dob(kol[i + 1][j + 1][fl][nfr][1], koler);
}
}
}
}
else if (fl)
{
if (s[i] == '1')
{
int nfl = fl;
if (l[i + 1] == '0') nfl = 0;
dob(dp[i + 1][j][nfl][fr][t], sm(koler, fx(2, val)));
mk[i + 1][j][nfl][fr][t] = 1;
dob(kol[i + 1][j][nfl][fr][t], koler);
}
else
if (l[i + 1] != '1')
{
dob(dp[i + 1][j][fl][fr][t], fx(2, val));
mk[i + 1][j][fl][fr][t] = 1;
dob(kol[i + 1][j][fl][fr][t], koler);
}
if (j != k)
{
if (s[i] == '0')
{
int nfl = fl;
if (l[i + 1] == '0') nfl = 0;
dob(dp[i + 1][j + 1][nfl][fr][1], sm(koler, fx(2, val)));
mk[i + 1][j + 1][nfl][fr][1] = 1;
dob(kol[i + 1][j + 1][nfl][fr][1], koler);
}
else
if (l[i + 1] != '1')
{
dob(dp[i + 1][j + 1][fl][fr][1], fx(2, val));
mk[i + 1][j + 1][fl][fr][1] = 1;
dob(kol[i + 1][j + 1][fl][fr][1], koler);
}
}
}
else if (fr)
{
if (s[i] == '0')
{
int nfr = fr;
if (r[i + 1] == '1') nfr = 0;
dob(dp[i + 1][j][fl][nfr][t], fx(2, val));
mk[i + 1][j][fl][nfr][t] = 1;
dob(kol[i + 1][j][fl][nfr][t], koler);
}
else
if (r[i + 1] != '0')
{
dob(dp[i + 1][j][fl][fr][t], sm(koler, fx(2, val)));
mk[i + 1][j][fl][fr][t] = 1;
dob(kol[i + 1][j][fl][fr][t], koler);
}
if (j != k)
{
if (s[i] == '1')
{
int nfr = fr;
if (r[i + 1] == '1') nfr = 0;
dob(dp[i + 1][j + 1][fl][nfr][1], fx(2, val));
mk[i + 1][j + 1][fl][nfr][1] = 1;
dob(kol[i + 1][j + 1][fl][nfr][1], koler);
}
else
if (r[i + 1] != '0')
{
dob(dp[i + 1][j + 1][fl][fr][1], sm(koler, fx(2, val)));
mk[i + 1][j + 1][fl][fr][1] = 1;
dob(kol[i + 1][j + 1][fl][fr][1], koler);
}
}
}
else
{
if (s[i] == '0')
{
dob(dp[i + 1][j][fl][fr][t], fx(2, val));
mk[i + 1][j][fl][fr][t] = 1;
dob(kol[i + 1][j][fl][fr][t], koler);
}
else
{
dob(dp[i + 1][j][fl][fr][t], sm(koler, fx(2, val)));
mk[i + 1][j][fl][fr][t] = 1;
dob(kol[i + 1][j][fl][fr][t], koler);
}
if (j != k)
{
if (s[i] == '0')
{
dob(dp[i + 1][j + 1][fl][fr][1], sm(koler, fx(2, val)));
mk[i + 1][j + 1][fl][fr][1] = 1;
dob(kol[i + 1][j + 1][fl][fr][1], koler);
}
else
{
dob(dp[i + 1][j + 1][fl][fr][1], fx(2, val));
mk[i + 1][j + 1][fl][fr][1] = 1;
dob(kol[i + 1][j + 1][fl][fr][1], koler);
}
}
}
}
else
{
if (fl && fr)
{
if (s[i] == '0')
{
if (r[i + 1] != '0')
{
int nfl = fl;
if (l[i + 1] == '0') nfl = 0;
dob(dp[i + 1][j][nfl][fr][t], sm(koler, fx(2, val)));
mk[i + 1][j][nfl][fr][t] = 1;
dob(kol[i + 1][j][nfl][fr][t], koler);
}
}
else
{
if (l[i + 1] != '1')
{
int nfr = fr;
if (r[i + 1] == '1') nfr = 0;
dob(dp[i + 1][j][fl][nfr][t], fx(2, val));
mk[i + 1][j][fl][nfr][t] = 1;
dob(kol[i + 1][j][fl][nfr][t], koler);
}
}
if (j != k)
{
if (s[i] == '1')
{
if (r[i + 1] != '0')
{
int nfl = fl;
if (l[i + 1] == '0') nfl = 0;
dob(dp[i + 1][j + 1][nfl][fr][0], sm(koler, fx(2, val)));
mk[i + 1][j + 1][nfl][fr][0] = 1;
dob(kol[i + 1][j + 1][nfl][fr][0], koler);
}
}
else
{
if (l[i + 1] != '1')
{
int nfr = fr;
if (r[i + 1] == '1') nfr = 0;
dob(dp[i + 1][j + 1][fl][nfr][0], fx(2, val));
mk[i + 1][j + 1][fl][nfr][0] = 1;
dob(kol[i + 1][j + 1][fl][nfr][0], koler);
}
}
}
}
else if (fl)
{
if (s[i] == '0')
{
int nfl = fl;
if (l[i + 1] == '0') nfl = 0;
dob(dp[i + 1][j][nfl][fr][t], sm(koler, fx(2, val)));
mk[i + 1][j][nfl][fr][t] = 1;
dob(kol[i + 1][j][nfl][fr][t], koler);
}
else
if (l[i + 1] != '1')
{
dob(dp[i + 1][j][fl][fr][t], fx(2, val));
mk[i + 1][j][fl][fr][t] = 1;
dob(kol[i + 1][j][fl][fr][t], koler);
}
if (j != k)
{
if (s[i] == '1')
{
int nfl = fl;
if (l[i + 1] == '0') nfl = 0;
dob(dp[i + 1][j + 1][nfl][fr][0], sm(koler, fx(2, val)));
mk[i + 1][j + 1][nfl][fr][0] = 1;
dob(kol[i + 1][j + 1][nfl][fr][0], koler);
}
else
if (l[i + 1] != '1')
{
dob(dp[i + 1][j + 1][fl][fr][0], fx(2, val));
mk[i + 1][j + 1][fl][fr][0] = 1;
dob(kol[i + 1][j + 1][fl][fr][0], koler);
}
}
}
else if (fr)
{
if (s[i] == '1')
{
int nfr = fr;
if (r[i + 1] == '1') nfr = 0;
dob(dp[i + 1][j][fl][nfr][t], fx(2, val));
mk[i + 1][j][fl][nfr][t] = 1;
dob(kol[i + 1][j][fl][nfr][t], koler);
}
else
if (r[i + 1] != '0')
{
dob(dp[i + 1][j][fl][fr][t], sm(koler, fx(2, val)));
mk[i + 1][j][fl][fr][t] = 1;
dob(kol[i + 1][j][fl][fr][t], koler);
}
if (j != k)
{
if (s[i] == '0')
{
int nfr = fr;
if (r[i + 1] == '1') nfr = 0;
dob(dp[i + 1][j + 1][fl][nfr][0], fx(2, val));
mk[i + 1][j + 1][fl][nfr][0] = 1;
dob(kol[i + 1][j + 1][fl][nfr][0], koler);
}
else
if (r[i + 1] != '0')
{
dob(dp[i + 1][j + 1][fl][fr][0], sm(koler, fx(2, val)));
mk[i + 1][j + 1][fl][fr][0] = 1;
dob(kol[i + 1][j + 1][fl][fr][0], koler);
}
}
}
else
{
if (s[i] == '1')
{
dob(dp[i + 1][j][fl][fr][t], fx(2, val));
mk[i + 1][j][fl][fr][t] = 1;
dob(kol[i + 1][j][fl][fr][t], koler);
}
else
{
dob(dp[i + 1][j][fl][fr][t], sm(koler, fx(2, val)));
mk[i + 1][j][fl][fr][t] = 1;
dob(kol[i + 1][j][fl][fr][t], koler);
}
if (j != k)
{
if (s[i] == '1')
{
dob(dp[i + 1][j + 1][fl][fr][0], sm(koler, fx(2, val)));
mk[i + 1][j + 1][fl][fr][0] = 1;
dob(kol[i + 1][j + 1][fl][fr][0], koler);
}
else
{
dob(dp[i + 1][j + 1][fl][fr][0], fx(2, val));
mk[i + 1][j + 1][fl][fr][0] = 1;
dob(kol[i + 1][j + 1][fl][fr][0], koler);
}
}
}
}
}
ll ans_nakanecto = 0;
dob(ans_nakanecto, dp[n][k][0][0][0]);
dob(ans_nakanecto, dp[n][k][0][0][1]);
dob(ans_nakanecto, dp[n][k][0][1][0]);
dob(ans_nakanecto, dp[n][k][0][1][1]);
dob(ans_nakanecto, dp[n][k][1][0][0]);
dob(ans_nakanecto, dp[n][k][1][0][1]);
dob(ans_nakanecto, dp[n][k][1][1][0]);
dob(ans_nakanecto, dp[n][k][1][1][1]);
cout << ans_nakanecto << endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
12672 KB |
Output is correct |
| 2 |
Correct |
11 ms |
12032 KB |
Output is correct |
| 3 |
Correct |
11 ms |
11392 KB |
Output is correct |
| 4 |
Correct |
11 ms |
10752 KB |
Output is correct |
| 5 |
Correct |
10 ms |
10112 KB |
Output is correct |
| 6 |
Correct |
10 ms |
9600 KB |
Output is correct |
| 7 |
Correct |
9 ms |
8960 KB |
Output is correct |
| 8 |
Correct |
9 ms |
8320 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
640 KB |
Output is correct |
| 2 |
Correct |
5 ms |
640 KB |
Output is correct |
| 3 |
Correct |
5 ms |
768 KB |
Output is correct |
| 4 |
Correct |
5 ms |
768 KB |
Output is correct |
| 5 |
Correct |
5 ms |
640 KB |
Output is correct |
| 6 |
Correct |
5 ms |
640 KB |
Output is correct |
| 7 |
Correct |
5 ms |
640 KB |
Output is correct |
| 8 |
Correct |
5 ms |
640 KB |
Output is correct |
| 9 |
Correct |
5 ms |
640 KB |
Output is correct |
| 10 |
Correct |
5 ms |
640 KB |
Output is correct |
| 11 |
Correct |
5 ms |
640 KB |
Output is correct |
| 12 |
Correct |
5 ms |
640 KB |
Output is correct |
| 13 |
Correct |
5 ms |
640 KB |
Output is correct |
| 14 |
Correct |
5 ms |
640 KB |
Output is correct |
| 15 |
Correct |
5 ms |
640 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
80 ms |
66552 KB |
Output is correct |
| 2 |
Correct |
67 ms |
54776 KB |
Output is correct |
| 3 |
Correct |
70 ms |
59128 KB |
Output is correct |
| 4 |
Correct |
103 ms |
77688 KB |
Output is correct |
| 5 |
Correct |
64 ms |
52728 KB |
Output is correct |
| 6 |
Correct |
103 ms |
77816 KB |
Output is correct |
| 7 |
Correct |
46 ms |
39288 KB |
Output is correct |
| 8 |
Correct |
70 ms |
58616 KB |
Output is correct |
| 9 |
Correct |
15 ms |
15104 KB |
Output is correct |
| 10 |
Correct |
67 ms |
55416 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
12672 KB |
Output is correct |
| 2 |
Correct |
11 ms |
12032 KB |
Output is correct |
| 3 |
Correct |
11 ms |
11392 KB |
Output is correct |
| 4 |
Correct |
11 ms |
10752 KB |
Output is correct |
| 5 |
Correct |
10 ms |
10112 KB |
Output is correct |
| 6 |
Correct |
10 ms |
9600 KB |
Output is correct |
| 7 |
Correct |
9 ms |
8960 KB |
Output is correct |
| 8 |
Correct |
9 ms |
8320 KB |
Output is correct |
| 9 |
Correct |
5 ms |
640 KB |
Output is correct |
| 10 |
Correct |
5 ms |
640 KB |
Output is correct |
| 11 |
Correct |
5 ms |
768 KB |
Output is correct |
| 12 |
Correct |
5 ms |
768 KB |
Output is correct |
| 13 |
Correct |
5 ms |
640 KB |
Output is correct |
| 14 |
Correct |
5 ms |
640 KB |
Output is correct |
| 15 |
Correct |
5 ms |
640 KB |
Output is correct |
| 16 |
Correct |
5 ms |
640 KB |
Output is correct |
| 17 |
Correct |
5 ms |
640 KB |
Output is correct |
| 18 |
Correct |
5 ms |
640 KB |
Output is correct |
| 19 |
Correct |
5 ms |
640 KB |
Output is correct |
| 20 |
Correct |
5 ms |
640 KB |
Output is correct |
| 21 |
Correct |
5 ms |
640 KB |
Output is correct |
| 22 |
Correct |
5 ms |
640 KB |
Output is correct |
| 23 |
Correct |
5 ms |
640 KB |
Output is correct |
| 24 |
Correct |
80 ms |
66552 KB |
Output is correct |
| 25 |
Correct |
67 ms |
54776 KB |
Output is correct |
| 26 |
Correct |
70 ms |
59128 KB |
Output is correct |
| 27 |
Correct |
103 ms |
77688 KB |
Output is correct |
| 28 |
Correct |
64 ms |
52728 KB |
Output is correct |
| 29 |
Correct |
103 ms |
77816 KB |
Output is correct |
| 30 |
Correct |
46 ms |
39288 KB |
Output is correct |
| 31 |
Correct |
70 ms |
58616 KB |
Output is correct |
| 32 |
Correct |
15 ms |
15104 KB |
Output is correct |
| 33 |
Correct |
67 ms |
55416 KB |
Output is correct |
| 34 |
Correct |
90 ms |
71672 KB |
Output is correct |
| 35 |
Correct |
45 ms |
38904 KB |
Output is correct |
| 36 |
Correct |
63 ms |
52856 KB |
Output is correct |
| 37 |
Correct |
31 ms |
12160 KB |
Output is correct |
| 38 |
Correct |
28 ms |
25464 KB |
Output is correct |
| 39 |
Correct |
87 ms |
65400 KB |
Output is correct |
| 40 |
Correct |
25 ms |
23424 KB |
Output is correct |
| 41 |
Correct |
74 ms |
61688 KB |
Output is correct |
| 42 |
Correct |
88 ms |
70264 KB |
Output is correct |
| 43 |
Correct |
86 ms |
67064 KB |
Output is correct |
| 44 |
Correct |
85 ms |
65016 KB |
Output is correct |
| 45 |
Correct |
42 ms |
36860 KB |
Output is correct |
| 46 |
Correct |
77 ms |
62456 KB |
Output is correct |
| 47 |
Correct |
83 ms |
64888 KB |
Output is correct |
| 48 |
Correct |
60 ms |
49912 KB |
Output is correct |
| 49 |
Correct |
15 ms |
14516 KB |
Output is correct |
| 50 |
Correct |
94 ms |
71288 KB |
Output is correct |
| 51 |
Correct |
57 ms |
47608 KB |
Output is correct |
| 52 |
Correct |
59 ms |
50680 KB |
Output is correct |
| 53 |
Correct |
98 ms |
75256 KB |
Output is correct |
| 54 |
Correct |
48 ms |
40444 KB |
Output is correct |
| 55 |
Correct |
91 ms |
72568 KB |
Output is correct |
| 56 |
Correct |
102 ms |
76152 KB |
Output is correct |
| 57 |
Correct |
24 ms |
23040 KB |
Output is correct |
| 58 |
Correct |
86 ms |
69880 KB |
Output is correct |
