c++ - nCk modulo p when n % p or k % p == 0 -

i'm trying solve coding challenge on hacker rank requires 1 calculate binomial coefficients mod prime, i.e.

nchoosek(n, k, p)  

i'm using code answer works first 3 sets of inputs begins failing on 4th. stepped through in debugger , determined issue arises when:

n % p == 0 || k % p == 0 

i need know how modify current solution handle specific cases n % p == 0 or k % p == 0. none of answers i've found on stack exchange seem address specific case. here's code:

#include <iostream> #include <fstream>  long long factorialexponent(long long n, long long p) {     long long ex = 0;         {         n /= p;         ex += n;     }while(n > 0);     return ex; }  unsigned long long modularmultiply(unsigned long long a, unsigned long long b, unsigned long p) {   unsigned long long a1 = (a >> 21), a2 = & ((1ull << 21) - 1);   unsigned long long temp = (a1 * b) % p;   // doesn't overflow under assumptions   temp = (temp << 21) % p;                  // neither   temp += (a2 * b) % p;                       // nor   return temp % p; }  unsigned long long modularinverse(unsigned long long k, unsigned long m) {     if (m == 0) return (k == 1 || k == -1) ? k : 0;     if (m < 0) m = -m;     k %= m;     if (k < 0) k += m;     int neg = 1;     unsigned long long p1 = 1, p2 = 0, k1 = k, m1 = m, q, r, temp;     while(k1 > 0) {       q = m1 / k1;       r = m1 % k1;       temp = q*p1 + p2;       p2 = p1;       p1 = temp;       m1 = k1;       k1 = r;       neg = !neg;     }     return neg ? m - p2 : p2; }  // preconditions: 0 <= k <= min(n,p-1); p > 1 prime unsigned long long choosemodtwo(unsigned long long n, unsigned long long k, unsigned long p) {     // reduce n modulo p     n %= p;      // trivial checks     if (n < k) {          return 0;     }      if (k == 0 || k == n) {         return 1;     }      // 0 < k < n, save bit of work if k > n/2     if (k > n/2) {         k = n-k;     }     // calculate numerator , denominator modulo p     unsigned long long num = n, den = 1;     for(n = n-1; k > 1; --n, --k)     {         num = modularmultiply(num, n, p);         den = modularmultiply(den, k, p);     }      den = modularinverse(den,p);     return modularmultiply(num, den, p); }  // preconditions: 0 <= k <= n; p > 1 prime long long choosemodone(long long n, long long k, const unsigned long p) {     // small k, no recursion necessary     if (k < p) return choosemodtwo(n,k,p);     unsigned long long q_n, r_n, q_k, r_k, choose;     q_n = n / p;     r_n = n % p;     q_k = k / p;     r_k = k % p;      choose = choosemodtwo(r_n, r_k, p);     // if exponent of p in choose(n,k) isn't determined 0     // before calculation gets serious, short-cut here:     // if (choose == 0) return 0;     return modularmultiply(choose, choosemodone(q_n, q_k, p), p);  }  unsigned long long modularbinomialcoefficient(unsigned long long n, unsigned long long k, const unsigned long p) {     // deal trivial cases first     if (k < 0 || n < k) return 0;     if (k == 0 || k == n) return 1;     // check whether choose(n,k) divisible p     if (factorialexponent(n, p) > factorialexponent(k, p) + factorialexponent(n - k, p)) return 0;     // if it's not divisible, generic work     return choosemodone(n, k, p); }  int main() {    //std::ifstream fin ("input03.txt");   std::ifstream fin ("test.in");    int kmod = 1000003;   int t;   fin >> t;   int n = t;   //std::cin >> t;    unsigned long long n, k;   unsigned long long a, b;   int result[n];   int index = 0;    while (t--) {      fin >> n >> k;      = modularbinomialcoefficient(n - 3, k, kmod);     b = modularbinomialcoefficient(n + k, n - 1, kmod);      // (1 / (n + k) * nck(n - 3, k) * nck(n + k, n - 1)) % 1000003     unsigned long long x = modularmultiply(a, b, kmod);     unsigned long long y = modularmultiply(x, modularinverse((n + k), kmod), kmod);      result[index] = y;     index++;   }    for(int = 0; < n; i++) {     std::cout << result[i] << "\n";   }    return 0; }  input: 6 90 13 65434244 16341234 23424244 12341234 424175 341198 7452123  23472 56000168 16000048  output: 815483 715724 92308 903465 241972 0 <-- incorrect, should be: 803478 

constraints:
4 <= n <= 10^9
1 <= k <= n

you can use lucas' theorem reduce problem ceil(log_p(n)) subproblems k, n < p: write n = n_m * p^m + ... + n_0 , k = k_m * p^m + ... + k_0 in base p (n_i, k_i < p digits), have

c(n,k) = prod(i = 0 m, c(n_i, k_i))  (mod p) 

the subproblems easy solve, because every factor of k! has inverse modulo p. algorithm runtime complexity o(p log(n)), better of ivaylo's code in case of p << n, if understand correctly.

int powmod(int x, int e, int p) {     if (e == 0) return 1;     if (e & 1) return (long long)x * powmod(x, e - 1, p) % p;     long long rt = powmod(x, e / 2, p);     return rt * rt % p; }  int binom_coeff_mod_prime(int n, int k, int p) {     long long res = 1;     while (n || k) {         int n = n % p, k = k % p;         (int = n - k + 1; <= n; ++i)             res = res * % p;         (int = 1; <= k; ++i)             res = res * powmod(i, p - 2, p) % p;         n /= p;         k /= p;     }     return res; }