### PROBLEM LINK:

### DIFFICULTY:

SIMPLE

### PREREQUISITES:

Combination, Sum of Binomial Coefficients

### PROBLEM:

For a given value N, Find the sum of all Combination(N,k) where k varies from 1 to N

### QUICK EXPLANATION:

Σ(Combination(N,k)) for 0 <= k <= N is the sum of binomial coefficients in the expansion of (1+x)^N which is equal to 2^N

### EXPLANATION:

When there are k chairs in the classroom, we can select k students out of N to sit on them. Number of ways of selecting k students from N is given by Combination(N,k). As number of chairs vary from 1 to N, our task is to find: Σ(Combination(N,k)) for 1 <= k <= N.

Σ(Combination(N,k)) for 0 <= k <= N is the sum of binomial coefficients in the expansion of (1+x)^N which is equal to 2^N. In our current problem, number of chairs varies from 1 to N so we should remove the case when no chair is present in the class. Hence all we have to calculate is 2^N - 1

We can use Right-to-left binary method for modular exponentiation to calculate (2^N % MOD) in log N time. Since N is not very large it is also possible to pre-calculate all values of 2^N.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here

Tester’s solution can be found here and here