computing the binorminal coefficient

n(n-1)..(n-k+1) / k(k-1)..2

$\frac{1}{2}$

First thinking is to do reduction of fraction on the nominator for each denominator.
Store a array of n, n-1, .., n-k+1,
and another array k, k-1, ..2,
Acutally since every two continuous numbers must have one has factor to 2
    every three continuous numbers must have one has factor to 3
and so on,maybe we can get a algorithm to find those numbers have i as factor easily

Actually since  14*13*12*11*10*9*8*7*6*5*4*3*2
the even number after divide by two is  7, 6,5,4,3,2, hence starting from  (n-k+1), it has factor (n-k+1)/2, (n-k+1)/2+1, (n-k+1)/2 +2.....for even numbers starting from (n-k+1)



use the equation  (n k) = (n-1 k) + (n-1 k-1)
Two dimentional DP, result in O(nk) complexity.