807. Count All Valid Pickup/Delivery Options (Modulo 10^9+7)

Given n orders, each with a pickup Pi and delivery Di (Pi must come before Di), count the number of valid sequences of all 2n events, mod 10^9+7.

Input: A non-negative integer n.

Output: Integer mod 10^9+7.

Examples

Example 1

Input: 1
Output: 1
Explanation: Only P1 D1.

Example 2

Input: 2
Output: 6
Explanation: Six valid orderings.

Example 3

Input: 3
Output: 90
Explanation: 90 valid orderings.