Matching

Every beginner in an arena game needs to be assigned a mentor. When a beginner registers for the game he gets assigned to a random mentor who has already registered before him.

Only one person can register at a time and a mentor cannot be assigned to more than one beginner.

Find the total number of sequences in which N beginners and N mentors can register for the game such that whenever a beginner registers he can be assigned some mentor as opponent.

Input Format

The only line of of input contains an integer N.

Sample Output

Print in a single line the number of valid sequences. Since the output can be very big, print it modulo 1000,000,007.

Sample Input

3

Sample Output

5

Explanation

There are 5 possible sequences in which 3 beginners and 3 mentors can register for the game such that condition sought for is satisfied.

Following are the five possible registration sequences. B denotes a beginner while M indicates a Mentor. The one who registers earlier has been shown earlier in the list.

1 . MBMBMB
2. MBMMBB
3. MMBMBB
4. MMBBMB
5. MMMBBB

Constraints
1 <= N <= 100000