<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>

# 2024/09/17
# 面试前刷Doordash高频题目
#
# 这题有点意思
# 只需要输出组合个数就行
# 以n等于2为例，相当于我们有两对组合(P1,D1)和(P2,D2), 然后必须按照顺序去依次取
# 感觉最优解是一个数学问题
# n * n * (n - 1)... 难点在于，某个组合可能空了，就不确定下一个要乘的系数是否减一
# 所以导致DP有点难处理
# DFS 肯定可以
# 共2n层，每层表示当前放那个
# P可以直接放，D的话要看之前对应的P是否放过
# 每个node最多可以try 2n
# 但这相当于把所有的解都输出了，肯定超时
# 有思路了，插入法，别忘了一个空格可以放入两个元素，比如 _ P1 _ D1 _ -> P1 P2 D2 D1 都放在中间那个
# M[i] means the num of possible sequences for n order
# M[i] = (C(2 * (i - 1) + 1)(2) + (2 * (i - 1) + 1)) * M[i - 1] = ((2*i - 1) * (2*i - 2) // 2 + 2 * (i - 1) + 1) * M[i - 1]
# M[1] = 1
# 果然是数学问题
class Solution:
    def countOrders(self, n: int) -> int:
        M = [0] * (n + 1)

        M[1] = 1
        mod = pow(10, 9) + 7

        for i in range(2, n + 1):
            num_spots = 2 * (i - 1) + 1
            M[i] = (num_spots * (num_spots - 1) // 2 + num_spots) * M[i - 1] % mod

        return M[n]
16500