Non-Crossing Cat Pairing

There are (2n) cats arranged in a circle. You want to pair them up by tying their tails with a rope such that no two ropes cross. This is equivalent to finding the number of ways to draw non-intersecting chords between (2n) points on a circle, which is given by the (n)-th Catalan number: [ C_n = \frac{1}{n+1}\binom{2n}{n} ] Since the number of ways can be very large, output the answer modulo (10^9+7).

inputFormat

The input consists of a single integer (n) ((1 \le n \le 10^5) for instance), representing that there are (2n) cats arranged in a circle.

outputFormat

Output a single integer which is the number of non-crossing pairing ways modulo (10^9+7).

sample

1

1