Calculate nCr(n,m) mod k for large n efficiently

I need to calculate nCr(n,m) % k for large n (n <= 10^7) efficiently.

Here is my try:

int choose(int n, int m, int k) {
  if (n==m || m==0)
    return 1 % k;

  return (choose(n-1, m-1, k) + choose(n-1, m , k)) % k;
}

It calculates some amount of combinations mod k: nCr(n,m) % k by exploiting pascals identity.

This is too inefficient for large n (try choose(100, 12, 223092870)), I'm not sure if this can be speeded up by memoization or if some totally different number theoretic approach is necessary.

I need this to be executed efficiently for large numbers instantly which is why I'm not sure if memoization is the solution.

Note: k doesn't have to be a prime!