# 1359. Count All Valid Pickup and Delivery Options

## Problem Statement

<br>

Given `n` orders, each order consist in pickup and delivery services.&#x20;

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

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

&#x20;

**Example 1:**

<pre><code><strong>Input: n = 1
</strong><strong>Output: 1
</strong><strong>Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: n = 2
</strong><strong>Output: 6
</strong><strong>Explanation: All possible orders: 
</strong>(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.
</code></pre>

**Example 3:**

<pre><code><strong>Input: n = 3
</strong><strong>Output: 90
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= n <= 500`

## Intuition

```
Approach:

n=2
 _P1_D1_

No for P2 D2 
We have folowing options

1st position 
P2-> D2 can sit on 1 2 3
2nd
2 3
3rd
3

3 2 1 = 6 options

therefore x*(x+1)/2 = 6 find x

But what is x
1 1
2 3
3 5

x = 2*(n-1)
Hence do a recusion 
```

### Links

<https://leetcode.com/problems/count-all-valid-pickup-and-delivery-options/description/>

### Video Links

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    long long mod = 1e9+7;
    vector<int> dp;

    long long solve(int n){
        if(n==1||n==0)
            return 1;
        
        else if( dp[n] != -1)return dp[n];
        return dp[n] = (n*(2*n-1)*solve(n-1))%mod;
    }

    int countOrders(int n) {
        dp.resize(1001 , -1);
        return solve(n);
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/dynamic-programming/general/1359.-count-all-valid-pickup-and-delivery-options.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.