题目告诉你在一个排列中，相邻两个数的大小关系。问你排列可能有多少种情况。
DP。
f[i][j]表示将i个数按照前面i-1个大小关系排列且最后一个数位j的排列数有多少个。
这样对于新加入的一个数i+1，我们直接枚举第i+1个数在所有的i+1个数为第几大即可。
注意加入sum数组，不然时间复杂度就是O(N^3)了。
注意不要每次取模，注意不需要long long。注意时间常数。
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 1010
#define M 1000000007
using namespace std; int f[maxn][maxn],sum1[maxn],sum2[maxn];
char s[maxn]; int count(int x)
{
if (x<M) return x;
return x-M;
} int main()
{
while (scanf("%s",s+)!=EOF)
{
memset(f,,sizeof f);
memset(sum1,,sizeof sum1);
memset(sum2,,sizeof sum2);
f[][]=,sum1[]=,sum2[]=;
for (int i=; s[i]; i++)
{
for (int j=; j<=i+; j++)
{
if (s[i]=='?') f[i+][j]=count(sum1[j-]+sum2[j]);
else if (s[i]=='I') f[i+][j]=sum1[j-];
else if (s[i]=='D') f[i+][j]=sum2[j];
}
sum1[]=f[i+][];
for (int j=; j<=i+; j++) sum1[j]=count(sum1[j-]+f[i+][j]);
sum2[i+]=f[i+][i+];
for (int j=i; j>; j--) sum2[j]=count(sum2[j+]+f[i+][j]);
}
int ans=,n=strlen(s+)+;
for (int i=; i<=n; i++) ans=count(ans+f[n][i]);
printf("%d\n",ans);
}
return ;
}