hdu 4055 dp

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;
 }