# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
320088 | keta_tsimakuridze | Tents (JOI18_tents) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long n,m,k,i,dp[3005][3-05];
int main(){
cin>>n>>m;
dp[0][0]=1;
for(k=1;k<=max(n,m);k++)
dp[k][0]=dp[0][k]=1;
for(k=1;k<=n;k++){
for(i=1;i<=m;i++){
dp[k][i]=dp[k-1][i];
if(i>=2) dp[k][i]+=dp[k-1][i-2]%mod*(i*(i-1))/2%mod;
dp[k][i]+=4*i*dp[k-1][i-1]%mod;
if(k>=2) dp[k][i]+=dp[k-2][i-1]%mod*i%mod*(k-1)%mod;
dp[k][i]%=mod;
// cout<<k<<" "<<i<<" "<<dp[k][i]<<endl;
} }
cout<<(dp[n][m]-1+mod)%mod;
}