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;
typedef long long LL;
const LL MOD = 1000000007;
LL powmod(LL a, LL n){
if(n == 0) return 1;
if(n % 2) return (a * powmod(a, n-1)) % MOD;
LL c = powmod(a, n/2);
return (c * c) % MOD;
}
LL inv(LL a){
return powmod(a, MOD-2);
}
LL fact[11000];
LL invfact[11000];
int main(){
LL a, b;
cin >> a >> b;
fact[0] = invfact[0] = 1;
for(LL i = 1; i < 11000; i++){
fact[i] = (i * fact[i-1]) % MOD;
invfact[i] = inv(fact[i]);
}
LL smth[a+1][b+1];
for(int i = 0; i <= a; i++){
for(int j = 0; j <= b; j++){
if((i + j) % 3 != (a + b) % 3) continue;
LL cur = 0;
for(int k = 0; k <= i && k <= j; k++){
LL z = powmod(4,k);
z = (z * invfact[k]) % MOD;
z = (z * invfact[i-k]) % MOD;
z = (z * invfact[j-k]) % MOD;
cur = (cur + z) % MOD;
}
smth[i][j] = cur;
}
}
LL ans = 0;
for(LL c = 0; c <= a && c*2 <= b; c++){
for(LL d = 0; c + 2*d <= a && c*2 + d <= b; d++){
LL cur = (fact[a] * fact[b]) % MOD;
cur = (cur * inv(powmod(2,c))) % MOD;
cur = (cur * inv(powmod(2,d))) % MOD;
cur = (cur * invfact[c]) % MOD;
cur = (cur * invfact[d]) % MOD;
cur = (cur * smth[a - c - 2*d][b - c*2 - d]) % MOD;
ans = (ans + cur) % MOD;
}
}
ans--;
ans %= MOD;
if(ans < 0) ans += MOD;
cout << ans << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |