<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 factorial(int x, int modulo)
    {
        long long result = 1;

        for(int i = 2; i <= x; i++)
            result = (result * i) % modulo;

        return result;
    }

    int countOrdersRec(int pickupUsed, int deliveryUsed, int n, vector<vector<int>>& cache, int modulo)
    {
        if(pickupUsed == n)
            return factorial(n - deliveryUsed, modulo);

        if(cache[pickupUsed][deliveryUsed] != -1)
            return cache[pickupUsed][deliveryUsed];

        long long possiblePickups = n - pickupUsed;
        int result = (possiblePickups * countOrdersRec(pickupUsed + 1, deliveryUsed, n, cache, modulo)) % modulo;

        if (pickupUsed > deliveryUsed)
        {
            long long possibleDeliveries = pickupUsed - deliveryUsed;
            int resultDelivery = (possibleDeliveries * countOrdersRec(pickupUsed, deliveryUsed + 1, n, cache, modulo)) % modulo;
            result = (result + resultDelivery) % modulo;
        }

        cache[pickupUsed][deliveryUsed] = result;
        return result;
    }

    //9.16
    int countOrders(int n) {
        vector<vector<int>> cache(n + 1, vector<int>(n + 1, -1));
        int modulo = pow(10, 9) + 7;
        return countOrdersRec(0, 0, n, cache, modulo);
        //result(P=0, D=0, n, n)
            //result(P=1, D=0, n, n)
                //result(P=1, D=1, n, n) +
                //result(P=2, D=0, n, n)
                    //result(P=3, D=0, n, n)
                    //result(P=2, D=1, n, n);
        
        //PPDD
        //P1 P2 D1 D2
        //P2 P1 D1 D2
        //P2 P1 D2 D1
        //P1 P2 D2 D1

        //P D P D
        //P1 D1 P2 D2
        //P2 D2 P1 D1

    }
};

//result(0, 0, 2)
    //2 * result(1, 0, 2)
        //pickup --> result(2, 0, 2)
        //delivery --> result()
21100