/*
二項係数のライブラリ(mod計算)
・modpow(a,n):a^nを計算
・COMinit():二項係数のライブラリを使うための下準備をする
・COM(n,r):nCrを計算(n,r<=3×10^6位まで)
(modinv(a):aの逆元を計算)
*/
#define mod 1000000007ll

long long modpow(long long a, long long n)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
long long modinv(long long a)
{
    return modpow(a, mod - 2);
}
vector<long long> fact(3000001);    //fact[i]=(i!)
vector<long long> factinv(3000001); //factinv[i]=(i!)^-1
void COMinit()
{
    long long now = 1;
    fact[0] = 1;
    factinv[0] = modinv(0);
    for (long long i = 1; i < 3000001; i++)
    {
        now *= i;
        now %= mod;
        fact[i] = now;
        factinv[i] = modinv(now);
    }
}
long long COM(long long n, long long r)
{
    if (n < r)
        return 0;
    if (n < 0 || r < 0)
        return 0;
    if (n == r)
        return 1;
    if (r == 0)
        return 1;
    long long ans = fact[n];
    ans *= factinv[r];
    ans %= mod;
    ans *= factinv[n - r];
    ans %= mod;
    return ans;
}