### Problem Link : Contest Practice

**Author and Editorialist** : Arun Prasad geek_geek

### Difficulty:

Easy

### PREREQUISITES:

Modular Arithmetic,Combinatorics,Repeated Squaring

### PROBLEM

Given n items , find number of ways to choose k different items.

### QUICK EXPLANATION

You have to find the value of nCk it will give you number of ways of choosing k items from n items

print nCk % mod (mod = 1000000007)

### EXPLANATION

nck = (n!)/((n-k)! * k!)

now you cannot store n! in an array as it can be very big instead

you can store n!%mod in an array

since mod is a prime number you have to use fermatâ€™s theorem to calculate the value of modular inverse of ((k!)%mod) and ((n-k)!%mod)

store the value of n!%mod in an array , and calculate inverse factorial for each n by using the formula

inv_factorial(n) = exp(n,mod-2,mod) (use repeated squaring for faster answers)

store all in an array

if n is greater tha k :

nCk = (fact(n)*inv_fact(n-k)*inv_fact(k))%mod

if n is lesser than k

You cannot choose k items from n if k is greater than n

hence answer is 0