<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:
    def countOrders(self, n: int) -> int:
        # brute force: count options to choose from
        # N PN choices for first character
        # next character can be D1 or PN not chosen
        # this method would take n^n time and have n^n space
        # can we instead simplify this?
        # we could cache the options
        # we don't need a list of chosen things, just the number of available options
        # at the last point there will only be one available option
        # at the 2nd last point there could be 2 options or 1 option
        # ..1 option if 1P 1D left, 2 if 2D left. Can't have 2P left. 
        # 3rd is even more options..
        # it shouldn't matter what ps are used and what ds are used. the answer for the number of possibilities should be the same
        # in a valid sub sequence.
        # so for possibil starting at i = 0: there are 0,0 there are n options to choose: 
        # so n * the posibilities for the other n-1 characters
        # (1, 0)
        # note that p is always greater than d
        # at 1 0 we can either theres 1 option of adding a d (1) * dp(1, 1) or n - 1 options of adding a p-> (n-1) * (2, 0)
        # at (1, 1) we can add a 
        # at (4,2) we can have there is 2 options of adding a d  2 * dp(4,3) or n - 4 options of adding a p (n-4) * d(5,2)
        dp = [[-1] * (n+1) for _ in range(n+1)]

        def dfs(p, d):
            if dp[p][d] != -1:
                return dp[p][d]
            ret = 0
            if d == n:
                ret = 1
            else:
                if p < n: # we can add pickups
                    ret += (n - p) * dfs(p+1, d)
                if d < p: # we can add deliveries
                    ret += (p - d) * dfs(p, d+1)
            dp[p][d] = ret
            return ret
        return dfs(0, 0) % (10**9 + 7)

192600