#include <bits/stdc++.h>
#define int long long
#define REP(i,o,n) for(int i=o;i<n;i++)
#define pb push_back
#define fi first
#define se second
#define FORI(v) for(auto i:v)
#define FORJ(v) for(auto j:v)
#define SETIO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
using pii = pair<int, int>;
const int mod = 1e9+7;
const int mi2 = (mod+1)/2;
int memo[400][400][400];
int memo2[4000][4000];
// Rem is dependent on zero and one?????
int dp(int zero, int one, int rem) {
if(zero<0)return 0;
if(one<0)return 0;
if(rem<0)return 0;
if(rem==0){
int a = 1;
REP(i,0,one)a*=4,a%=mod;
return a;
}
int &ans=memo[zero][one][rem];
if(ans!=-1)return ans;
ans=0;
ans=dp(zero-2,one,rem-1)*(((zero*(zero-1)))%mod); // Ambil 2
ans%=mod;
ans*=mi2;
ans%=mod;
ans+=dp(zero-1,one+1,rem-1)*((zero)%mod); // Ambil satu baru
ans%=mod;
ans+=dp(zero,one-1,rem-1)*((one)%mod); // Sambung yang lama
ans%=mod;
ans+=dp(zero,one,rem-1); // _Nothing_
ans%=mod;
return ans;
}
int ncr(int n, int r){
if(n<r)return 0;
if(n<0)return 0;
if(r<0)return 0;
if(n==r)return 1;
if(n==0)return 1;
if(r==0)return 1;
if(r==1)return n;
if(n==1)return 1;
auto&ans=memo2[n][r];
if(ans!=-1)return ans;
return ans=((ncr(n-1,r)+ncr(n-1,r-1))%mod);
}
#undef int
int main()
#define int long long
{
int h, w;cin>>h>>w;
memset(memo,-1,sizeof memo);
memset(memo2,-1,sizeof memo2);
// int ans=0;
// REP(i,0,h+1){
// int res=ncr(h,i);
// res*=dp(w,0,h-i);
// res%=mod;
// ans+=res;
// ans%=mod;
// }
// ans--;
// if(ans==-1)ans=(mod-1);
int ans=dp(w,0,h);
if(ans==0)ans=mod-1;
else ans--;
cout<<ans<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
227 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
227 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
