Balanced Binary Strings

Given an integer N, determine how many balanced binary strings of length 2N can be formed. A balanced binary string is defined as a binary string that has exactly N zeros and N ones, and for every prefix of the string, the number of zeros is at least as many as the number of ones.

This problem can be formulated in combinatorial terms. In fact, the answer is the N-th Catalan number, which can be expressed as:

\( C_N = \frac{1}{N+1} \binom{2N}{N} \)

Since the result can be very large, output the answer modulo \(10^9+7\).

Example:

• If N = 2, then the answer is 2.
• If N = 4, then the answer is 14.

inputFormat

The input is read from the standard input and consists of a single integer N (1 ≤ N ≤ 1000).

outputFormat

Output a single integer which is the number of balanced binary strings of length 2N, taken modulo \(10^9+7\).

2

2