Fast Expontiation iterative version

long pow(long a, long x)
{
      long res = 1;
      while(x>0){
      if(x%2!=0)
      {
            res = res* a;
       }
      x = x/2;
      a = a*a;
 }
}

How to calculate nCk%p

1) Calculating nCk: simply calculate:
numerator = n(n-1)...(n-k+1)
deno = k(k-1)...k!
ans = num/deno

But what if num and deno is high and over flow may occur, you can use
nCk = nC(k-1) (n-k+1)/k repeatedly. . Both can be calculated in O(k) steps

2) With modulo involved, suppose you are calculating modulo a big prime P. Then we know Z_p is a field and therefore multiplicative inverse exist i.e. for any number x<P, there exist x^-1 also less than P s.t. (x*x^-1)%P = 1.

So, to find nC(k-1)*(n-k+1)k^-1, we need to find k^-1. 

Before moving on let's review the fermat's little theorem, which states that for any a<p, a^(P-1) %P= 1. (The theorem is valid for a>p as well, but for our case a<p suffices). P is a  prime here. So what is k^-1%P?
k^(P-1)%P = 1 => k^-1 = k^-1k^(P-1) = k^(P-2)

Quick little fact about run time in Competitive programming

10^7 steps will take around 1 sec roughly. Though it depends on what the steps are and in codechef timelimit in the problem is for 1 test file which can contain multiple test cases.
At time of execution multiple test files may be run which is why the execution time shown may be greater than the time limit in the problem