【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5729
【题目大意】
给出一个n*m的方格框，可以在单位矩形中添加两种对角线的线，使得其变得稳定，问使得其变成稳定图形的方案数。
【题解】
稳定状态指的是在n*m范围内每行每列都有一个固定的格子，并且联动，计算合法的情况非常的复杂，难以枚举，因此我们可以枚举非法情况，从组合数中减去即可。非法情况即将图形划分为合法部分和非法部分，注意枚举全面。
【代码】
#include <cstdio>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
const long long mod=1e9+7;
long long dp[15][15][105],c[105][105];
int n,m;
long long pow(long long a,long long b){long long tmp=1; a%=mod;while(b){if(b&1)tmp=tmp*a%mod;a=a*a%mod;b>>=1;}return tmp;
}
int main(){rep(i,100){c[i][0]=c[i][i]=1;rep(j,i-1)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;}c[0][0]=dp[1][0][0]=dp[0][1][0]=1;rep(i,10)rep(j,10){if(i==1||j==1){dp[i][j][i+j-1]=1;continue;}rep(k,i*j){dp[i][j][k]=c[i*j][k];rep(ii,i)for(int jj=0;jj<=j;jj++){if(i+j==ii+jj)continue;for(int kk=0;kk<=k;kk++){long long tmp=c[i-1][ii-1]*c[j][jj]%mod;tmp=tmp*dp[ii][jj][kk]%mod;tmp=tmp*c[(i-ii)*(j-jj)][k-kk]%mod;dp[i][j][k]=(dp[i][j][k]+mod-tmp)%mod;}}}}while(~scanf("%d%d",&n,&m)){long long ans=0;rep(i,n*m)ans=(ans+pow(2,i)*dp[n][m][i]%mod)%mod;printf("%lld\n",ans);}return 0;
}
