c++ - Finding binomial coefficient for large n and k modulo m -

i want compute nck mod m following constraints:

n<=10^18

k<=10^5

m=10^9+7

i have read article:

but here value of m 1009. hence using lucas theorem, need calculate 1009*1009 different values of acb a,b<=1009

how above constraints. cannot make array of o(m*k) space complexity given constraints.

help!

just use fact

(n, k) = n! / k! / (n - k)! = n*(n-1)*...*(n-k+1)/[k*(k-1)*...*1]

so have 2*k=2*10^5 factors. inverse of number can use suggestion of kfx since m prime.

Ben