Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.8 kB
1
Indexable
Never
#define _CRT_SECURE_NO_WARNINGS
#include <functional>
#include <algorithm>
#include <iostream>
#include <memory.h>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <assert.h>
#include <bitset>
#include <string>
#include <cstdio>
#include <math.h>
#include <complex>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <bitset>
#include <map>
using namespace std;

#define ll long long
#define mp make_pair
#define pb push_back

typedef pair<int, int> pii;

#ifdef _DEBUG
const int N = 100;
#else
const int N = 5010;
#endif

const int MOD = 1e9+7;

int n;
int dp[N][N];
int f[N][3];
string s;

int solve(int i, int j) {
    if (dp[i][j] != -1) return dp[i][j];
    if (i > n && j > n) {
        return dp[i][j] = 1;
    }
    int posM, posW, posU;
    posU = f[max(i, j)][2];
    posM = min(f[i][0], posU);
    posW = min(f[j][1], posU);
    if (posM == posW) dp[i][j] = solve(posM + 1, posW + 1);
    else {
        dp[i][j] = 0;
        if (posM != n) dp[i][j] += solve(posM + 1, posW);
        if (posW != n) dp[i][j] += solve(posM, posW + 1);
        if (dp[i][j] >= MOD) dp[i][j] -= MOD;
    }
    return dp[i][j];
}

int main()
{
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
    cin >> n;
    cin >> s;
    f[n][0] = f[n][1] = f[n][2] = n;
    for (int i = n - 1; i >= 0; i--) {
        f[i][0] = f[i + 1][0];
        f[i][1] = f[i + 1][1];
        f[i][2] = f[i + 1][2];
        if (s[i] == 'M') f[i][0] = i;
        else if (s[i] == 'W') f[i][1] = i;
        else f[i][2] = i;
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) dp[i][j] = -1;
    }
    cout << solve(0, 0);
	return 0;
}