### PROBLEM LINK:

**Author:** Diwakar Bhardwaj

**Tester:** Aditya Kumar

**Editorialist:** Shubham Kabra

### DIFFICULTY:

EASY-MEDIUM

### PREREQUISITES:

Dynamic Programming, Permutation & Combination, Inverse Modulo

### PROBLEM:

For given numbers **N**, **I** and **K**, we have to find the number of sorted subsets where **I** comes at position **K** that can be formed by *set{1,2,…N}*.

### EXPLANATION:

Let’s fix the position of I_{th} number at K_{th} position as given in the problem.

Now, we have to find total number of possible subsets that can be formed with given conditions.

Firstly, choose the numbers for the first K-1 positions as they are blank right now. We have to fill these positions with first I-1 numbers as we have to keep the subset in sorted form.

So, total number of ways for choosing the number from I-1 numbers for K-1 positions is ^{(I-1)}C_{(K-1)}.

Now, for the remaining numbers from I+1 to N, it is not necessary that they appear in the subset or not. So, for every number *greater than* I, either the number appears in subset or not. So, permutation for either choosing each number or not is 2 and for total N-I numbers it will be 2^{(N-I)}.

Hence, total number of required subsets are ^{(I-1)}C_{(K-1)} * 2^{(N-I)}.

*We have to give output as (^{(I-1)}C_{(K-1)} * 2^{(N-I)})\%(10^9+7).*

Now, we just have to calculate ^{I-1}C_{K-1} for each query (keeping the number of queries 10^6 into consideration); the best solution is to pre compute each and every case of ^{I-1}C_{K-1}.

For, pre computation we can use the formula for computing ^nc_r:

.

### OPTIMAL COMPLEXITY:

\mathcal{O}(N*K + Q)

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

Author’s solution can be found here.

Tester’s solution can be found here.