# Nhut Nguyen # Problem statement

Given `n` orders, each order consists of pickup and delivery services.

Count all valid pickup/delivery possible sequences such that delivery(i) is always after 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 Delivery 2.
``````

## Example 3

``````Input: n = 3
Output: 90
``````

## Constraints

• `1 <= n <= 500`.

# Understand the problem

At first, I did not fully understand the problem. Especially when Example 3 did not give an explanation.

Finally here was what I understood from Example 1 and Example 2 to rephrase the problem for easier solving.

Each value of `n` gives you `2*n` slots for `P_i` and `D_i` (`1 <= i <= n`)

``````[ ][ ][P_i][ ]...[D_i][ ].
``````

You have to put `D_i` after `P_i` for all `1 <= i <= n`. Return the number of ways for such arrangement.

# Solution: Finding the pattern

## Example 2

You have four slots for `n = 2`: `[ ][ ][ ][ ]`. You are asked to count how many ways to putting `P1, D1, P2, D2` there.

You can only put a "pickup" in the first slot. There are twos options: `P1` or `P2`.

• If you put `P1` in the first slot: `[P1][ ][ ][ ]`, you can put `D1` in any slot of the three remained. Once `D1` is in place, there are only two slots remaining for putting `P2` and `D2`. This is the case of `n = 1` with only one solution.
• The same behavior if you put `P2` in the first slot.

In total you have `2 * 3 * 1 = 6` ways.

## Example 3

You have six slots for `n = 3`: `[ ][ ][ ][ ][ ][ ]`. You are asked to count how many ways to putting `P1, D1, P2, D2, P3, D3` there.

Again, you can only put a "pickup" in the first slot. There are three options: `P1`, `P2`, or `P3`.

• If you put `P1`in the first slot: `[P1][ ][ ][ ][ ][ ]`, you can put `D1` in any slot of the five remained. Once `D1` is in place, there are four slots remaining for putting `P2`, `D2`, `P3`, and `D3`. This is the case of `n = 2` with six ways of arrangement.
• The same behavior if you put `P2` or `P3` in the first slot.

In total, you have `3 * 5 * 6 = 90` ways, which matches the Output of Example 3.

Now you found the pattern.

Let us call the function that counts the result `countOrders(n)`.

Here is the recursive relationship between `countOrders(n)` and `countOrders(n - 1)`.

``````countOrders(n) = n * (2*n - 1) * countOrders(n - 1).
``````

## Code

``````#include <iostream>
const int P = 1000000007;
int countOrders(int n) {
long result = 1;
for (int i = 2; i <= n; i++) {
result = (result * i) % P;
result = (result * (2*i - 1)) % P;
}
return result;
}

int main() {
std::cout << countOrders(1) << std::endl;
std::cout << countOrders(2) << std::endl;
std::cout << countOrders(3) << std::endl;
}
``````
``````Output:
1
6
90
``````

## Complexity

• Runtime: `O(n)`.
• Extra space: `O(1)`.

## Implementation notes

Algorithmically, the following implementation might be valid since it reflects what you computed and what the problem requested.

``````const int P = 1000000007;
int countOrders(int n) {
unsigned long long result = 1;
for (int i = 2; i <= n; i++) {
result = i * (2*i - 1) * result;
}
return result % P;
}
``````

But results of many multiplications during this loop might already exceed the integer type's limit in C++. This means you might get unexpected values during this loop. And the final result might be incorrect.

To avoid such unexpected overflow, the modulo `10^9 + 7` is taken whenever a multiplication is performed in the Solution above.

On the other hand, the Modular arithmetic property makes sure the final result was computed as expected.

``````((a % P) * b) % P = (a * b) % P.
``````