1381. Count All Valid Pickup Delivery Orders

There are n orders, each consisting of a pickup and a delivery, and a delivery may only occur after its own pickup. Count the number of valid sequences of all 2n events, and return the answer modulo 1000000007.

Input: A JSON object {"n": <number of orders>}.

Output: Return the number of valid sequences modulo 1000000007.

Examples

Input: {"n":2}
Output: 6
Explanation: Six valid sequences exist for two orders.

Input: {"n":3}
Output: 90
Explanation: Ninety valid sequences exist for three orders.

Constraints

• 1 <= n <= 500

Asked by