# AOJ 2439. Hakone

,

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2439

さすがICPC・JAG非公式難易度表でたくさん星付いてるだけあって、良い問題だった。

## implementation

#include <cstdio>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
const int mod = 1e9+7;
int main() {
int n; scanf("%d", &n);
vector<char> s(n); repeat (i,n) scanf(" %c", &s[i]);
vector<vector<ll> > cur(n+1, vector<ll>(n+1)); // dp : (requiring-up) \times (dangling-down) \to (count)
vector<vector<ll> > prv(n+1, vector<ll>(n+1));
cur[0][0] = 1;
for (char c : s) {
cur.swap(prv);
repeat (i,n+1) repeat (j,n+1) {
if (c == '-') {
cur[i][j] = prv[i][j];
} else if (c == 'U') {
cur[i][j] = 0;
;                          cur[i][j] += prv[i][j] * i; // up
if (i-1 >= 0 and j-1 >= 0) cur[i][j] += prv[i-1][j-1]; // down
cur[i][j] %= mod;
} else if (c == 'D') {
cur[i][j] = 0;
if (i+1 < n+1 and j+1 < n+1) cur[i][j] += prv[i+1][j+1] * (i+1) * (j+1); // up
;                            cur[i][j] += prv[i][j] * j; // down
cur[i][j] %= mod;
}
}
}
printf("%lld\n", cur[0][0]);
return 0;
}