Combination of large numbers

I tried to solve it but everytime it’s giving me TLE because of the large input size.
How to find the combination of large numbes like 10^6?
Link:https://www.hackerrank.com/contests/prosort12/challenges/energy

For these kinds of problems generate on paper about 6,7 first answers and give it to oeis.org :slight_smile:
They are Catalan numbers.
Cn = 2n!/((n+1)!n!)
So just use the fact that 10^9+7 is prime, and count for i=(1…2n), (i!)%(10^9+7) and it’s multiplicative inverse.
That’s all.

1 Like
//