#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mn = 1e6, smth = 3;
int dp[mn][smth][smth];
signed main() {
int n, mod;
cin >> n >> mod;
string s;
cin >> s;
dp[0][0][0] = 1;
// l then p
for (int i = 0; i < n; i++) {
for (int j = 0; j < smth; j++) {
for (int k = 0; k < smth; k++) {
if (j != 2) {
dp[i + 1][j + 1][max(0ll, k - 1)] += dp[i][j][k];
dp[i + 1][j + 1][max(0ll, k - 1)] %= mod;
}
if (k != 2) {
dp[i + 1][max(0ll, j - 1)][k + 1] += dp[i][j][k];
dp[i + 1][max(0ll, j - 1)][k + 1] %= mod;
}
}
}
}
int ls = 0, ps = 0;
int prev = 0;
for (int i = 0; i < n; i++) {
// cout << i << " " << prev << " " << ls << " " << ps << "\n";
if (s[i] == 'P') {
for (int j = 0; j + ls + 1 < smth; j++)
for (int k = 0; k + max(0ll, ps - 1) < smth; k++) {
prev += dp[n - i - 1][j][k];
prev %= mod;
}
ps++;
ls--;
ls = max(ls, 0ll);
} else {
ps--;
ls++;
ps = max(ps, 0ll);
}
}
// for (int i = 0; i < smth; i++)
// for (int j = 0; j < smth; j++)
// cout << i << " " << j << " " << dp[3][i][j] << "\n";
cout << (prev + 1) % mod << "\n";
}
# | 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... |