Count All Valid Pickup and Delivery Options

Given n orders, each order consist in pickup and delivery services.

Count all valid pickup/delivery possible sequences such that delivery(i) is always after of pickup(i).

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: n = 1
Output: 1
Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.

Example 2:

Input: n = 2
Output: 6
Explanation: All possible orders: 
(P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1) and (P2,D2,P1,D1).
This is an invalid order (P1,D2,P2,D1) because Pickup 2 is after of Delivery 2.

Example 3:

Input: n = 3
Output: 90

Constraints:

• 1 <= n <= 500

// Case: n = 1
// Result: 1 (P1 D1)

// Case: n = 2
// Place P2 D2 to 1 result from case n=1: (__ P1 __ D1 __), there are 3 spaces to place to
// The result will be:
// (P2 D2 P1 D1) (P2 P1 D2 D1) (P2 P1 D1 D2)
// (P1 P2 D2 D1) (P1 P2 D1 D2)
// (P1 D1 P2 D2)

// We can come up with the formula

// spaceNum = (n-1)*2 + 1
// result = 1 + 2 + ... + spaceNum = spaceNum * (spaceNum+1) / 2
// Hence,

// spaceNum = (n-1)*2 + 1 = 3
// result = spaceNum * (spaceNum+1) / 2 = 3 * 4 / 2 = 6
// Result: 6

// Case: n = 3
// Place P3 D3 to 6 results from case n=2: (__ P2 __ D2 __ P1 __ D1 __), (__ P2 __ P1 __ D2 __ D1 __),..., (__ P1 __ D1 __ P2 __ D2 __)
// Hence,

// spaceNum = (n-1)*2 + 1 = 5
// result = spaceNum * (spaceNum+1) / 2 = 5 * 6 / 2 = 15
// Apply this P3 D3 place to 6 results from case n = 2
// result = 15 * 6 = 90
class Solution {
    public int countOrders(int n) {
        long MODULO = (long) (1e9 + 7);
        long ans = 1;
        for (int i = 2; i <= n; i++) {
            int spaceNum = (i - 1) * 2 + 1;
            ans *= spaceNum * (spaceNum + 1) / 2;
            ans %= MODULO;
        }
        return (int) ans;
    }
}