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

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