Finding binomial coefficient for large n and k modulo m
<p>I want to compute nCk mod m with following constraints:</p>

<p>n&lt;=10^18</p>

<p>k&lt;=10^5</p>

<p>m=10^9+7</p>

<p>I have read this article:</p>

<p><a href="https://stackoverflow.com/questions/3537360/calculating-binomial-coefficient-nck-for-large-n-k">Calculating Binomial Coefficient (nCk) for large n &amp; k</a></p>

<p>But here value of m is 1009. Hence using Lucas theorem, we need only to calculate 1009*1009 different values of aCb where a,b&lt;=1009</p>

<p>How to do it with above constraints.
I cannot make a array of O(m*k) space complexity with given constraints.</p>

<p>Help!</p>