记录编号	156230	评测结果	AAAAAAAAAA
题目名称	[CF 295D] Greg和洞穴	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.669 s
提交时间	2015-04-03 16:30:22	内存使用	62.00 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int SIZEN=2010;
const LL MOD=1000000007;
LL realmod(LL x){
	x%=MOD;
	if(x<0) x+=MOD;
	return x;
}
int N,M;
LL R[SIZEN][SIZEN],T[SIZEN][SIZEN];;
LL S[SIZEN],MS[SIZEN];
void calc_sum(int i){
	S[0]=MS[0]=0;
	for(int j=1;j<=M;j++){
		S[j]=realmod(S[j-1]+R[i][j]);
		MS[j]=realmod(MS[j-1]+R[i][j]*j);
	}
}
LL get(LL m){
	LL sum=realmod(S[m]*(m+1));
	sum-=realmod(MS[m]);
	return realmod(sum);
}
void DP(void){
	for(int i=2;i<=M;i++){
		R[1][i]=1;
		T[1][i]=1;
	}
	calc_sum(1);
	for(int i=2;i<=N;i++){
		for(int j=2;j<=M;j++){
			R[i][j]=get(j);
			T[i][j]=realmod(R[i][j]-(S[j]-S[j-1]));
		}
		calc_sum(i);
		for(int j=2;j<=M;j++){
			R[i][j]=realmod(R[i][j]+R[i-1][j]);
			T[i][j]=realmod(T[i][j]+T[i-1][j]);
		}
	}
}
void work(void){
	LL ans=0;
	for(int i=1;i<=N;i++){
		for(int j=2;j<=M;j++){
			LL t=realmod(R[i][j]*T[N+1-i][j]);
			t=realmod(t*(M+1-j));
			ans=realmod(ans+t);
		}
	}
	//printf("%I64d\n",ans);
	printf("%lld\n",ans);
}
int main(){
	freopen("gregandcaves.in","r",stdin);
	freopen("gregandcaves.out","w",stdout);
	scanf("%d%d",&N,&M);
	DP();
	work();
	return 0;
}