Submission #767298

#TimeUsernameProblemLanguageResultExecution timeMemory
7672981075508020060209tcTents (JOI18_tents)C++14
100 / 100
83 ms82768 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
const int mod=1e9+7;
int n;int m;
int dp[5010][5010];
int cn2(int x){
return ((x*(x-1))/2)%mod;
}


signed main(){
cin>>n>>m;
dp[0][m]=1;
for(int H=1;H<=n;H++){
    for(int W=0;W<=m;W++){

        dp[H][W]=dp[H-1][W];

        dp[H][W]=(dp[H][W]+dp[H-1][W+1]*4*(W+1) )%mod;

        dp[H][W]=(dp[H][W]+dp[H-1][W+2]*cn2(W+2))%mod;

        if(H>=2){
            dp[H][W]=(dp[H][W]+dp[H-2][W+1]*(W+1)%mod*(H-1))%mod;
        }
    }
}
int ans=0;
for(int i=0;i<=m-1;i++){
    ans=(ans+dp[n][i])%mod;
}
cout<<ans<<endl;



}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...