#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
int n, dp[maxn][3][3], m;
string s;
int add (int x, int y){
if (x + y >= m) return x + y - m;
if (x + y < 0) return x + y + m;
return x + y;
}
int main (void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
cin >> s;
dp[0][0][1] = 1;
dp[0][0][2] = 1;
dp[0][1][0] = 1;
dp[0][1][1] = 1;
dp[0][1][2] = 1;
dp[0][2][0] = 1;
dp[0][2][1] = 1;
dp[0][2][2] = 1;
for (int i = 1; i <= n; i++){
dp[i][0][1] = dp[i - 1][1][0];
dp[i][0][2] = dp[i - 1][1][1];
dp[i][1][0] = dp[i - 1][0][1];
dp[i][1][1] = add(dp[i - 1][0][2], dp[i - 1][2][0]);
dp[i][1][2] = add(dp[i - 1][0][2], dp[i - 1][2][1]);
dp[i][2][0] = dp[i - 1][1][1];
dp[i][2][1] = add(dp[i - 1][2][1], dp[i - 1][0][2]);
dp[i][2][2] = add(dp[i - 1][1][2], dp[i - 1][2][1]);
}
int prije = 0;
int sufl = 0, sufp = 0;
for (int i = 0; i < s.size(); i++){
if (s[i] == 'L'){
sufl++;
sufp = max(sufp - 1, 0);
}
else{
int staril = sufl, starip = sufp;
sufl++;
sufp = max(sufp - 1, 0);
if (sufl <= 2 and sufp <= 2)prije = add(prije, dp[n - i - 1][2 - sufl][2 - sufp]);
sufl = staril, sufp = starip;
sufp++;
sufl = max(sufl - 1, 0);
}
//cout << sufl << " " << sufp << endl;
}
prije = add(prije, 1);
cout << prije << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |