Hakone Ekiden is one of the Japanese New Year's traditions. In Hakone Ekiden, 10 runners from each team aim for the goal while connecting the sashes at each relay station. In the TV broadcast, the ranking change from the previous relay station is displayed along with the passing order of each team at the relay station. So, look at it and tell us how many possible passage orders for each team at the previous relay station. The number of possible transit orders can be very large, so answer by the remainder divided by 1,000,000,007.



Input

The input is given in the form:

> n
> c1
> c2
> ...
> cn
>

The number n (1 ≤ n ≤ 200) representing the number of teams is on the first line, and the ranking changes from the previous relay station in order from the first place on the following n lines. If it is'`U`', the ranking is up, if it is'`-`', the ranking is not changed) is written.

Output

Please output in one line by dividing the number of passages that could have been the previous relay station by 1,000,000,007.

Examples

Input

3
-
U
D


Output

1


Input

5
U
U
-
D
D


Output

5


Input

8
U
D
D
D
D
D
D
D


Output

1


Input

10
U
D
U
D
U
D
U
D
U
D


Output

608


Input

2
D
U


Output

0
#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <stack>
#include <climits>
#include <deque>
#include <bitset>
#include <cassert>
#include <ctime>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
//const int dy[]={-1,0,1,0},dx[]={0,1,0,-1};
// adjust problem by problem
const double EPS=1e-8;
const double PI=acos(-1.0);
#ifdef __GNUC__
int popcount(int n){return __builtin_popcount(n);}
int popcount(ll n){return __builtin_popcountll(n);}
#endif
#ifndef __GNUC__
template<class T> int popcount(T n){int cnt=0;while(n){if(n%2)cnt++;n/=2;}return cnt;}
#endif
template<class T>int SIZE(T a){return a.size();}
template<class T>string IntToString(T num){string res;stringstream ss;ss<<num;return ss.str();}
template<class T>T StringToInt(string str){T res=0;for(int i=0;i<SIZE(str);i++)res=(res*10+str[i]-'0');return res;}
template<class T>T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template<class T>T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T> void PrintSeq(T &a,int sz){for(int i=0;i<sz;i++){cout<<a[i];if(sz==i+1)cout<<endl;else cout<<' ';}}
bool EQ(double a,double b){return abs(a-b)<EPS;}
void fastStream(){cin.tie(0);std::ios_base::sync_with_stdio(0);}
vector<string> split(string str,char del){
  vector<string> res;
  for(int i=0,s=0;i<SIZE(str);i++){
    if(str[i]==del){if(i-s!=0)res.push_back(str.substr(s,i-s));s=i+1;}
    else if(i==SIZE(str)-1){res.push_back(str.substr(s));}
  }
  return res;
}

const int mod = 1000000000+7;
int N;
char field[210];
ll dp[210][210][210];

ll dfs(int pos,int u,int d){
  if(dp[pos][u][d]>=0)return dp[pos][u][d];
  ll res = 0;
  if(pos == N){
    if(u == 0 && d == 0)res = 1;
  }
  else{
    if(field[pos] == '-')res = dfs(pos+1,u,d);
    else if(field[pos]=='U'){
      // ここに割り当て可能なのは、ここより下にあるDと、ここより上にあるUのうちどれかひとつ
      if(u>0)res = (res + (dfs(pos+1,u-1+1,d)*u)%mod )%mod;
      // ここで割り当てるDは下にあるDのうちどれか一つ
      res = (res + (dfs(pos+1,u+1,d+1))%mod)%mod;
    }
    else if(field[pos]=='D'){
      // ここに割り当て可能なのは、ここより下にあるDと、ここより上にあるU
      // このdは消化されたものとして扱う
      if(d>0){
        // 今回のパターンは、どれに割り当てられたかで場合分けが必要
        if(u>0)res = (res + (dfs(pos+1,u-1,d-1)*u)%mod)%mod;
        res = (res + (dfs(pos+1,u,d))%mod)%mod;
        res = (res * d) % mod;
      }
    }
  }
  return dp[pos][u][d] = res;
}

int main(){

  cin>>N;
  for(int i=0;i<N;i++)cin>>field[i];
  memset(dp,-1,sizeof(dp));
  cout<<dfs(0,0,0)<<endl;
  
  return 0;
}