C++(clang++ 11.0.1) 解法, 执行用时: 154ms, 内存消耗: 35700K, 提交时间: 2022-10-31 22:26:32

#include<bits/stdc++.h>
#define ls u<<1
#define rs u<<1|1
#define fi first
#define se second
#define min amin
#define max amax
#define pb push_back
#define pq priority_queue
#define vt vector
#define lb(x) (x&-x)
#define sub(i,j) ((1LL*i-1LL*j)%k+k)%k
std::mt19937 rnd(233);
using namespace std;
using ll=long long;
using node=array<int,2>;
using nnode=array<int,3>;
//inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+(c^'0');c=getchar();}return x*f;}
template<typename T=int>T read(){T x;cin>>x;return x;}
template<typename U,typename V>auto min(U x,V y){return x<y?x:y;}
template<typename U,typename V>auto max(U x,V y){return x>y?x:y;}
template<typename U,typename...V>auto min(U x,V...y){return min(x,min(y...));}
template<typename U,typename...V>auto max(U x,V...y){return max(x,max(y...));}
template<typename U,typename V>bool cmin(U &x,V y){return x>y?x=y,true:false;}
template<typename U,typename V>bool cmax(U &x,V y){return x<y?x=y,true:false;}
constexpr int mod=1e9+7;
//int qpow(int x,int n=mod-2){int y=1;for(;n;n>>=1,x=1LL*x*x%p)if(n&1)y=1LL*y*x%p;return y;}
inline ll qpow(ll a,ll n=mod-2){ ll ans = 1;while(n){if(n&1){ans*=a;}a*=a;n>>=1;}return ans;}
constexpr int N=3e3+10;
constexpr int inf=1e9;
constexpr double eps=1e-4;
const int Size=3005;
int n,m,dp[Size][Size];
void solve() {
	n=read();
	m=read();
	for(int i=0; i<=n; i++)	dp[i][0]=1;
	for(int i=0; i<=m; i++)	dp[0][i]=1;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			dp[i][j]=dp[i-1][j];
			dp[i][j]=(dp[i][j]+4ll*j%mod*dp[i-1][j-1]%mod)%mod;
			if(j>=2)dp[i][j]=(dp[i][j]+(ll)j*(j-1)/2%mod*dp[i-1][j-2]%mod)%mod;
			if(i>=2)dp[i][j]=(dp[i][j]+(ll)j*(i-1)%mod*dp[i-2][j-1]%mod)%mod;
		}
	}
	printf("%d",(dp[n][m]-1+mod)%mod);
}
signed main(){
	cin.sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	solve();
//	for(int T=read();T--;solve());
}