Submission #405793

---

Source Code Expand

const int MOD = 1000000009;

// Calculates x raised to the y-th power modulo MOD
// xのy乗を、繰り返し二乗法というのを使って求める
long modPow(long x, long y)
{
    long r=1, a=x;
    while (y > 0) {
        if ( (y&1)==1 ) {
            r = (r * a) % MOD;
        }
        a = (a * a) % MOD;
        y /= 2;
    }
    
    return r;
}
// Modular multiplicative inverse through Fermat's little theorem:
// フェルマーの小定理より, a^-1 ≡ a^(p-2) (mod p) というのを使うらしい
// ただし、pが素数の時しか成り立たない
long modInverse(long x)
{
    return modPow(x, MOD-2);
}

// Modular division x / y, find modular multiplicative inverse of y
// and multiply by x.
long modDivision(long p, long q)
{
    return (p * modInverse(q)) % MOD;
}

// Binomial coifficient C(n,k) in O(k) time.
long C(long n, int k)
{
    if (k > n) {
        return 0;
    }
    long p = 1, q = 1;
    for (int i=1; i<=k; i++) {
        q = ( q * i) % MOD;
        p = ( p * (n - i + 1) ) % MOD;
    }
    return modDivision( p, q);
}

Submission Info

Judge Result