Submission #10216306

---

Source Code Expand

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
const int maxn = 9e5 + 7, md = 1e9 + 7;
ll inv[maxn], finv[maxn], fac[maxn], f[maxn], p2[maxn], p3[maxn];
ll N, M, K, m, k;
ll read(){
    int s = 0; char c = getchar();
    while (c > '9' || c < '0') c = getchar();
    while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
    return s;
}
ll ksm(ll a, int b){
    ll res = 1;
    while (b){
        if (b & 1) res = res * a % md;
        a = a * a % md;
        b >>=1 ;
    }
    return res;
}
void init(){
    fac[0] = fac[1] = 1; inv[1] = finv[1] = 1;
    p3[1] = 3;p3[0] = 1;
    for (int i = 2; i < maxn; i++) p3[i] = p3[i - 1] * 3 % md;
    for (int i = 2; i < maxn; i++){
        inv[i] = ( md - (md / i) * inv[md%i] % md) % md;
    }
    for (ll i = 1; i < maxn; i++) {
        fac[i] = fac[i - 1] * i % md;
    }
    finv[maxn - 1] = ksm(fac[maxn - 1], md - 2);
    for (ll i = maxn - 2; i >= 0; i--) finv[i] = finv[i + 1] * (i + 1) % md;
    
}
ll ans = 0;
ll getf(){
    ll res = 0;
    f[0] = p3[M];
    res = f[0];
    for (int i = 1; i <= M; i++)
        f[i] = (((((f[i - 1] * (N - 1 + i + k) % md + md) % md ) * inv[3]) % md) * inv[i] + md) % md, res = ((res + f[i]) % md + md) % md;
    return res;
}
ll C(int x, int y){
    return fac[x] * finv[y] % md * finv[x - y] % md;
}
int main(){
    N = read(), M = read(), K = read();
    init();
    for (k = 0; k <= K; k++) {
        ans = (ans + p3[K-k] * C(N - 1 + k, k) % md * getf() % md);
    }
    printf("%lld\n", ans % md);
    return 0;
}

Submission Info

Judge Result