You need a **faster way** to find the value of NCr.

Your method of finding NCr leads to a time complexity of O(N^2), which results in **TLE** for the final subtask, as **N** can be as big as 2*10^5.

A faster way to compute NCr is as follows:

- Notice that NCr = \frac{N!}{r!*(N-r)!}. So,
- Precompute all factorials upto N.
- Now, we just need to learn how to do the modulo under division sign. This can be achieved if we find the modular multiplicative inverse of r!*(N-r)! with respect to 10^9+7. This can be found in log(10^9+7) time every time.
- Thus, to get a particular NCr, we can get the factorials in constant time from the precomputed factorial array, and then multiply N! with the modular multiplicative inverse of the denominator.

You can refer to my submission here: https://www.codechef.com/viewsolution/28102111

Hope it helped