title: Calculating Binomial Coefficient (nCk) for large n & k
body: <p>I just saw this question and have no idea how to solve it. can you please provide me with algorithms , C++ codes or ideas? </p>
  
  <blockquote>
    <p>This is a very simple problem. Given the value of N and K, you need to tell us the value of the binomial coefficient C(N,K). You may rest assured that K &lt;= N and the maximum value of N is 1,000,000,000,000,000. Since the value may be very large, you need to compute the result modulo 1009.
    Input</p>
    
    <p>The first line of the input contains the number of test cases T, at most 1000. Each of the next T lines consists of two space separated integers N and K, where 0 &lt;= K &lt;= N and 1 &lt;= N &lt;= 1,000,000,000,000,000.
    Output</p>
    
    <p>For each test case, print on a new line, the value of the binomial coefficient C(N,K) modulo 1009.
    Example</p>
    
    <p>Input:<br/>
    3<br/>
    3 1<br/>
    5 2<br/>
    10 3</p>
    
    <p>Output:<br/>
    3<br/>
    10<br/>
    120<br/></p>
  </blockquote>