There are n distinct orders. Each order has one pickup event and one delivery event, and its pickup must occur before its delivery. Count all possible sequences of the 2 * n events that obey this rule. Return the count modulo 1000000007.
Example 1:
Input: n = 4
Output: 2520Explanation: There are 8! possible sequences of the eight distinct events. Requiring each of the four pickups to precede its delivery leaves 8! / 2^4 = 2520 valid sequences.
Example 2:
Input: n = 1
Output: 1Explanation: The only valid sequence picks up the order and then delivers it.
Example 3:
Input: n = 2
Output: 6Explanation: Of the 24 permutations of the four events, half put the first pickup before its delivery, and half of those also put the second pickup before its delivery. This leaves 6 valid sequences.
Constraints:
1 <= n <= 500