对于任意一个只含数字1~n的有序数字串{a1,a2,……,an}，比较数字串中所有相邻数字的大小，后者大于前者的用I表示，否则用D表示。例如，数字串{3,1,2,7,4,6,5},{2,1,3,7,4,6,5}和{3,1,2,7,5,6,4}就表示为'DIIDID'。"?"则表示两数的关系未知。例如，'?D'既有可能是ID，也有可能是‘DD’。现给出数字串的表达方式，请输出所有数字串的个数。 为避免数据过大，答案对1000000007取模后输出。
#include <iostream>
#include <vector>
#include <cstring>
using namespace std ;
const int N=1003;
#define int long long
const int mod =1e9+7;
char op[N] ;
int n,m,f[N][N],s[N][N] ;
void sov(){
int i,j;
f[1][1]=s[1][1]=1;
for(i=2;i<=n;i++)
for(j=1;j<=i;j++){
if(op[i]=='?') f[i][j] =s[i-1][i-1];
if(op[i]=='I') f[i][j]= s[i-1][j-1];
if(op[i]=='D')
f[i][j]=(s[i-1][i-1]-s[i-1][j-1]+mod)%mod;
s[i][j]=s[i][j-1]+f[i][j],s[i][j]%=mod;
}
cout<<s[n][n]<<endl;
}
signed main(){
while(cin>>(op+2)){
n=strlen(op+2)+1;
memset(f,0,sizeof f);
memset(s,0,sizeof s);
sov();
}
}