CareerCup

Approach 1 :

We precompute the value of factorial modulo p in an array..
then we get an expression of the form (a/b)%p
We evaluate this with the help of the euler phi function..

Approach 2:
Use Lucas theorem.. Much more elegant method..
For non-negative integers m and n and a prime p, the following congruence relation holds:

\binom{m}{n}\equiv\prod_{i=0}^k\binom{m_i}{n_i}\pmod p,

where

    m=m_kp^k+m_{k-1}p^{k-1}+\cdots +m_1p+m_0,

and

    n=n_kp^k+n_{k-1}p^{k-1}+\cdots +n_1p+n_0

are the base p expansions of m and n respectively. This uses the convention that \tbinom{m}{n} = 0 if m < n.