Submission #898472

#TimeUsernameProblemLanguageResultExecution timeMemory
898472maxFedorchukTents (JOI18_tents)C++17
100 / 100
174 ms62924 KiB
#include <bits/stdc++.h>
using namespace std;

const long long MOD=1e9+7;

const long long MX=3300;

long long dp[MX][MX];

long long cntdp(long long n,long long m)
{
    if(n<=0 || m<=0)
    {
        return 1;
    }

    if(dp[n][m])
    {
        return dp[n][m];
    }

    dp[n][m]=cntdp(n-1,m);

    dp[n][m]=(cntdp(n-1,m-1)*4*m+dp[n][m])%MOD;

    dp[n][m]=((cntdp(n-1,m-2)*(m*(m-1)/2))%MOD+dp[n][m])%MOD;

    dp[n][m]=((cntdp(n-2,m-1)*m*(n-1))%MOD+dp[n][m])%MOD;

    return dp[n][m];
}
int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    long long n,m;
    cin>>n>>m;

    cout<<(cntdp(n,m)-1+MOD)%MOD<<"\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...