Получаю WA в задаче по модулю: дробь n!/(k!(n-k)!) считаю обычным делением — где ошибка?

Принципиальная ошибка — обычное целочисленное деление / несовместимо с модульной арифметикой. После взятия остатков fact(n) и fact(k)*fact(n-k) это уже «перемешанные» по модулю числа, и a / b над ними не даёт правильный C(n,k) mod p. Деление по модулю — это умножение на обратный элемент, а не оператор /. На маленьких числах остатки случайно совпадают с настоящими значениями, поэтому ты и не замечал баг.

Правильно — заменить деление на умножение на обратный (через малую теорему Ферма, так как p простое):

long long binpow(long long a, long long b, long long m){
    long long r=1; a%=m;
    while(b){ if(b&1) r=r*a%m; a=a*a%m; b>>=1; }
    return r;
}
long long inv(long long a){ return binpow(a, MOD-2, MOD); }   // a^{-1} mod p

long long C(int n, int k){
    if (k < 0 || k > n) return 0;
    long long num = fact(n);
    long long den = fact(k) * fact(n-k) % MOD;
    return num * inv(den) % MOD;     // num * den^{-1}, НЕ num / den
}

Каждый вызов — O(n + log p). Если запросов много, предподсчитай fact[] и inv_fact[] один раз, тогда каждый C(n,k) — O(1).