hdu 4055

http://acm.hdu.edu.cn/showproblem.php?pid=4055

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;

const int mod=1000000007;
const int sizen=1010;
__int64 dp[sizen][sizen];
__int64 sum[sizen][sizen];
char str[sizen];

int main()
{
    int i,j;
    int len;
    while(scanf("%s",str)!=EOF)
    {
        
        dp[1][1]=sum[1][1]=1;
        len=strlen(str);
        for(i=2;i<=len+1;i++)
            for(j=1;j<=i;j++)
            {
                if(str[i-2]=='I')
                    dp[i][j]=sum[i-1][j-1]%mod;
                if(str[i-2]=='D')
                    dp[i][j]=(sum[i-1][i-1]-sum[i-1][j-1]+mod)%mod;
                if(str[i-2]=='?')
                    dp[i][j]=sum[i-1][i-1];
                sum[i][j]=(dp[i][j]+sum[i][j-1])%mod;
            }
        printf("%I64d\n",sum[len+1][len+1]);
    }
    return 0;
}