//递推求逆元
void init()
{
    fact[0] = 1;
    for (int i = 1; i <= 10000; i++)
    {
        fact[i] = fact[i - 1] * i % MOD;
    }
    finv[0] = finv[1] = inv[1] = 1;
    for (int i = 2; i <= 10000; i++)
    {
        inv[i] = ((-1 * (MOD / i) * inv[MOD % i] % MOD) + MOD) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
//计算组合
long long C(int n, int m)
{
    return fact[n] * finv[m] % MOD * finv[n - m] % MOD;
}