<p>Given <code>n</code> orders, each order consists of a pickup and a delivery service.</p>

<p>Count all valid pickup/delivery possible sequences such that delivery(i) is always after of&nbsp;pickup(i).&nbsp;</p>

<p>Since the answer&nbsp;may be too large,&nbsp;return it modulo&nbsp;10^9 + 7.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

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

<p><strong class="example">Example 3:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 500</code></li>
</ul>

class Solution {
public:
    int mod=1e9+7;
    long long int dp[501][501];
    long long int func(int pick,int del)
    {
        if(del<0||pick<0)return 0;//base case as it can't be negative
        
        if(del<pick)return 0; // condition to insure we are first picking then delivering 
        
        if(pick==0&&del==0)return 1;//everything finishes return 1
        
        if(dp[pick][del]!=-1)return dp[pick][del]; //memoization 
        
        long long int ans=0; // initializing the answer
        
        ans+=pick*func(pick-1,del); // if there are pick number of orders we have [pick]C1 = pick number of choices for selecting  and we have picked one so we do pick-1
        ans%=mod;
        
        ans+=(del-pick)*func(pick,del-1);// delivering : the number of items we have picked but not delivered is (del-pick) so we can select one item from these to deliver [del-pick]C1  =del-pick and we have delivered so del-1
        ans%=mod;
        
        return dp[pick][del]=ans;
        
    }
    int countOrders(int n) {
        memset(dp,-1,sizeof(dp));
        return func(n,n);// passing pick and del
    }
};
9500