void precalculate()
{
    fac[0] = 1;
    for(int i = 1 ; i < N ; i++) fac[i] = 1LL*i*fac[i-1] % MOD;
    for(int i = 0 ; i < N ; i++) ifac[i] = bigmod(fac[i] , MOD - 2);
    /// O ( n * log(MOD) )

    ifac[N-1] = bigmod(fac[N-1] , MOD - 2);
    for(int i = N-2 ; i >= 0 ; i--) ifac[i] = 1LL*ifac[i+1]*(i+1) % MOD;
    /// O(N)
}