# 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.
```