Given n orders, each order consist in pickup and delivery services. 
Count all valid pickup/delivery possible sequences such that delivery(i) is always after of pickup(i). 
Since the answer may be too large, return it modulo 10^9 + 7.
 
Example 1:
Input: n = 1
Output: 1
Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.

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

Example 3:
Input: n = 3
Output: 90

 
Constraints:

1 <= n <= 500

Difficulty: interview

Starter code:

class Solution:
    def countOrders(self, n: int) -> int:
        

Solutions:
class Solution:
    def countOrders(self, n: int) -> int:
        
        if n == 1:
            return 1
        
        
        p = (n-1)*2+1
        
        dp = [0 for i in range(n+1)]
        dp[1] = 1
        M= 10**9+7
        for i in range(2,n+1):
            
            p = (i-1)*2+1
            
            dp[i] = (dp[i-1]%M * ((p*(p+1))//2)%M)%M
        
        return dp[n]


class Solution:
    def countOrders(self, n: int) -> int:

        ans = 1
        MOD = 1000000007
        for i in range(2, n + 1):
            ans *= ((2 * i - 1) * (i - 1) + (2 * i - 1))
            ans %= MOD

        return ans


class Solution:
    def countOrders(self, n: int) -> int:
        if n <= 1:
            return n
        num_spots = (n*2) - 1
        return (((num_spots*(num_spots+1))//2) * self.countOrders(n-1)) % ((10**9)+7)


class Solution:
    def countOrders(self, n: int) -> int:
        F = [0, 1]
        
        for i in range(2, n+1):
            one_way = i * 2 - 1
            F.append(one_way * F[i-1] * i)
        
        return F[n]%(pow(10,9)+7)
            
        
        


import math
class Solution:
    def countOrders(self, n: int) -> int:
        MOD = 10**9 + 7
        
        dp = [0 for _ in range(n+1)]
        
        dp[1] = 1
        
        for i in range(2,n+1):
            N = (i-1)*2+1
            dp[i] = (N + math.factorial(N)//(math.factorial(N-2)*2)) * dp[i-1] % MOD
            
        return dp[n]


class Solution:
    # bottom-up
    def countOrders(self, n: int) -> int:
        dp = {}
        dp[1] = 1
        
        for i in range(2, n+1):
            num_digit, res = 2 * (i-1), 0
            for j in range(num_digit+1, 0, -1):
                res += j
            dp[i] = res * dp[i-1]
        
        return dp[n] % (10**9 + 7)

class Solution:
    def countOrders(self, n: int) -> int:
        dp = [0 for _ in range(n+1)]
        dp[1] = 1
        mod = 10 ** 9 + 7
        for i in range(2, n+1):
            spaces = (i-1) * 2 + 1
            permutations = sum(j for j in range(1, spaces+1))
            dp[i] = (dp[i-1] * permutations) % mod
        return dp[n]

class Solution:
    def countOrders(self, n: int) -> int:
        if n == 1:
            return 1
        else:
            positions = 2*(n-1) +1
            all_possib = 0
            for i in range(positions +1):
                possibilities = positions -i
                all_possib += possibilities
            return (all_possib * self.countOrders(n-1) % 1000000007)

class Solution:
    def countOrders(self, n: int) -> int:
        
        
        
        dp = [1 for i in range(n)]
        
        for i in range(1,n):
            sequence = i+1
            length = 2*(i)
            temp = sum([j for j in range(1,length+2)])
            dp[i] = temp*dp[i-1]
        
        print(dp)
        return dp[-1]%(10**9+7)

class Solution:
    def countOrders(self, n: int) -> int:
        dp = [0, 1]
        
        for i in range(2, n+1):
            res = dp[i-1] * (2*(i-1)+1) * (2*(i-1)+2)//2
            res = res%(10**9+7)
            dp.append(res)
        return dp[n]

class Solution:
    def countOrders(self, n: int) -> int:
        # 9:41
        # we just want to make sure delivery i happens before pick up i
        # we can save lot of recursive calls by using maths
        
#         n*[(n-1),1]
#                    n-2
                    
#         p,d
#         n,0
        
#         p=n
#         d=0
        
#         p=n-1
#         d=1
        
#         p=n-2   or p=n-1
#                d=0
#         d=2.
        
        # @lru_cache(None)
        # def factorial(x):
        #     fact=1
        #     for i in range(1,x+1):
        #         fact*=i
        #     return fact
        mod=10**9+7
        facts=[1]
        for i in range(1,n+1):
            facts.append(facts[-1]*i)
            
        # @lru_cache(None)
        # def ways(pickOptions,deliverOptions):
        #     nonlocal mod
        #     ans=0
        #     if pickOptions>0 and deliverOptions>0:
        #         ans+=ways(pickOptions-1,deliverOptions+1)*pickOptions
        #         ans+=ways(pickOptions,deliverOptions-1)*deliverOptions
        #     elif pickOptions>0 and deliverOptions==0:
        #         ans+=ways(pickOptions-1,deliverOptions+1)*pickOptions
        #     elif deliverOptions>0 and pickOptions==0:
        #         ans+=facts[deliverOptions]
        #     return ans%mod
        # return ways(n,0)
    
        dp=[[0]*(n+1) for _ in range(n+1)]
        for p in range(n+1):
            for d in range(n-p+1):
                if p>0 and d>0:
                    dp[p][d]+=((dp[p-1][d+1]*p)%mod)
                    dp[p][d]+=((dp[p][d-1]*d)%mod)
                elif p>0 and d==0:
                    dp[p][d]+=((dp[p-1][d+1]*p)%mod)
                elif d>0 and p==0:
                    dp[p][d]+=(facts[d]%mod)
        return dp[n][0]
    
                
                    
                
        
                
                
                
            
        
        
        
            
        


class Solution:
    def countOrders(self, n: int) -> int:
        # 9:41
        # we just want to make sure delivery i happens before pick up i
        # we can save lot of recursive calls by using maths
        
#         n*[(n-1),1]
#                    n-2
                    
#         p,d
#         n,0
        
#         p=n
#         d=0
        
#         p=n-1
#         d=1
        
#         p=n-2   or p=n-1
#                d=0
#         d=2.
        
        # @lru_cache(None)
        # def factorial(x):
        #     fact=1
        #     for i in range(1,x+1):
        #         fact*=i
        #     return fact
        mod=10**9+7
        facts=[1]
        for i in range(1,n+1):
            facts.append(facts[-1]*i)
            
        # @lru_cache(None)
        # def ways(pickOptions,deliverOptions):
        #     nonlocal mod
        #     ans=0
        #     if pickOptions>0 and deliverOptions>0:
        #         ans+=ways(pickOptions-1,deliverOptions+1)*pickOptions
        #         ans+=ways(pickOptions,deliverOptions-1)*deliverOptions
        #     elif pickOptions>0 and deliverOptions==0:
        #         ans+=ways(pickOptions-1,deliverOptions+1)*pickOptions
        #     elif deliverOptions>0 and pickOptions==0:
        #         ans+=facts[deliverOptions]
        #     return ans%mod
        # return ways(n,0)
    
        dp=[[0]*(n+1) for _ in range(n+1)]
        for p in range(n+1):
            for d in range(n+1):
                if d>n-p:continue
                if p>0 and d>0:
                    dp[p][d]+=((dp[p-1][d+1]*p)%mod)
                    dp[p][d]+=((dp[p][d-1]*d)%mod)
                elif p>0 and d==0:
                    dp[p][d]+=((dp[p-1][d+1]*p)%mod)
                elif d>0 and p==0:
                    dp[p][d]+=(facts[d]%mod)
        return dp[n][0]
    
                
                    
                
        
                
                
                
            
        
        
        
            
        


class Solution:
    def countOrders(self, n: int) -> int:
        MOD = int(1e9) + 7
        d = [[0] * (n + 2) for _ in range(n + 2)]
        d[0][0] = 1
        for i in range(n + 1):
            for j in range(i + 1):
                d[i + 1][j] = (d[i + 1][j]+ d[i][j] * (n - i)) % MOD
                d[i][j + 1] = (d[i][j + 1] + d[i][j] * (i - j)) % MOD
        return d[n][n - 1]



class Solution:
    def countOrders(self, n: int) -> int:
        # 9:41
        # we just want to make sure delivery i happens before pick up i
        # we can save lot of recursive calls by using maths
        
#         n*[(n-1),1]
#                    n-2
                    
#         p,d
#         n,0
        
#         p=n
#         d=0
        
#         p=n-1
#         d=1
        
#         p=n-2   or p=n-1
#                d=0
#         d=2.
        
        # @lru_cache(None)
        # def factorial(x):
        #     fact=1
        #     for i in range(1,x+1):
        #         fact*=i
        #     return fact
        mod=10**9+7
        facts=[1]
        for i in range(1,n+1):
            facts.append(facts[-1]*i)
        
        
        @lru_cache(None)
        def ways(pickOptions,deliverOptions):
            nonlocal mod
            ans=0
            if pickOptions>0 and deliverOptions>0:
                ans+=ways(pickOptions-1,deliverOptions+1)*pickOptions
                ans+=ways(pickOptions,deliverOptions-1)*deliverOptions
            elif pickOptions>0 and deliverOptions==0:
                ans+=ways(pickOptions-1,deliverOptions+1)*pickOptions
            elif deliverOptions>0 and pickOptions==0:
                ans+=facts[deliverOptions]
            return ans%mod
        return ways(n,0)
    
        # dp=[]
        # for p in range(n+1):
        #     for d in range()
        
                
                
                
            
        
        
        
            
        


class Solution:
    def countOrders(self, n: int) -> int:
        l = 2
        num = 1
        for i in range(2, n+1):
            num = sum(num*(l-hole+1) for hole in range(l+1))
            l += 2
        return num % (10**9+7)

class Solution:
    def countOrders(self, n: int) -> int:
        # 9:41
        # we just want to make sure delivery i happens before pick up i
        # we can save lot of recursive calls by using maths
        
#         n*[(n-1),1]
#                    n-2
                    
#         p,d
#         n,0
        
#         p=n
#         d=0
        
#         p=n-1
#         d=1
        
#         p=n-2   or p=n-1
#                d=0
#         d=2.
        
        @lru_cache(None)
        def factorial(x):
            fact=1
            for i in range(1,x+1):
                fact*=i
            return fact
        mod=10**9+7
        @lru_cache(None)
        def ways(pickOptions,deliverOptions):
            nonlocal mod
            ans=0
            if pickOptions>0 and deliverOptions>0:
                ans+=ways(pickOptions-1,deliverOptions+1)*pickOptions
                ans+=ways(pickOptions,deliverOptions-1)*deliverOptions
            elif pickOptions>0 and deliverOptions==0:
                ans+=ways(pickOptions-1,deliverOptions+1)*pickOptions
            elif deliverOptions>0 and pickOptions==0:
                ans+=factorial(deliverOptions)
            return ans%mod
        return ways(n,0)
        
                
                
                
            
        
        
        
            
        


class Solution:
    def countOrders(self, n: int) -> int:
        # 9:41
        # we just want to make sure delivery i happens before pick up i
        # we can save lot of recursive calls by using maths
        
#         n*[(n-1),1]
#                    n-2
                    
#         p,d
#         n,0
        
#         p=n
#         d=0
        
#         p=n-1
#         d=1
        
#         p=n-2   or p=n-1
#                d=0
#         d=2.
        
        
        pickup=n
        delivery=0
        def factorial(x):
            fact=1
            for i in range(1,x+1):
                fact*=i
            return fact
        mod=10**9+7
        @lru_cache(None)
        def ways(pick,deliver):
            nonlocal mod
            ans=0
            if pick>0 and deliver>0:
                ans+=ways(pick-1,deliver+1)*pick
                ans+=ways(pick,deliver-1)*deliver
            elif pick>0 and deliver==0:
                ans+=ways(pick-1,deliver+1)*pick
            elif deliver>0 and pick==0:
                ans+=factorial(deliver)
            return ans%mod
        return ways(n,0)
        
                
                
                
            
        
        
        
            
        


class Solution:
    def countOrders(self, n: int) -> int:
        # 9:41
        # we just want to make sure delivery i happens before pick up i
        # we can save lot of recursive calls by using maths
        
#         n*[(n-1),1]
#                    n-2
                    
#         p,d
#         n,0
        
#         p=n
#         d=0
        
#         p=n-1
#         d=1
        
#         p=n-2   or p=n-1
#                d=0
#         d=2.
        
        
        def factorial(x):
            fact=1
            for i in range(1,x+1):
                fact*=i
            return fact
        mod=10**9+7
        @lru_cache(None)
        def ways(pickOptions,deliverOptions):
            nonlocal mod
            ans=0
            if pickOptions>0 and deliverOptions>0:
                ans+=ways(pickOptions-1,deliverOptions+1)*pickOptions
                ans+=ways(pickOptions,deliverOptions-1)*deliverOptions
            elif pickOptions>0 and deliverOptions==0:
                ans+=ways(pickOptions-1,deliverOptions+1)*pickOptions
            elif deliverOptions>0 and pickOptions==0:
                ans+=factorial(deliverOptions)
            return ans%mod
        return ways(n,0)
        
                
                
                
            
        
        
        
            
        


class Solution:
    def countOrders(self, n: int) -> int:
        num = 1
        for i in range(2, n+1):
            num = sum(num*((i-1)*2-hole+1) for hole in range((i-1)*2+1))
        return num % (10**9+7)

class Solution:
    def countOrders(self, n: int) -> int:
        DP = [0]*(n+1)
        DP[1] = 1
        for i in range(2, n+1):
            newpos = ((i*2-1)+1)*(i*2-1)//2
            DP[i] = newpos*DP[i-1]
        
        return DP[-1]%(10**9+7)

class Solution:
    def countOrders(self, n: int) -> int:
        def solve(remaining, pending):
            # Base case: no remaining orders and one pending order
            if remaining == 0 and pending == 1:
                return 1
            
            # Memoization case
            if memo[remaining][pending] != -1:
                return memo[remaining][pending]
            
            count = 0
            
            # Recursive case 1: start a new order, there are remaining ways to do so
            if remaining > 0:
                count += remaining * solve(remaining - 1, pending + 1)
            
            # Recursive case 2: end an order; there are pending ways to do so
            if pending > 0:
                count += pending * solve(remaining, pending - 1)
            
            count %= MOD
            memo[remaining][pending] = count 
            return count
        
        MOD = 10**9 + 7
        memo = [[-1 for _ in range(n+1)] for _ in range(n+1)]
        return solve(n, 0)

class Solution:
    def countOrders(self, n: int) -> int:
        '''
        # Notes:
            example n = 3
                                P1         P2     P3 
                             P2    P3   D1
                        P3   D1  D2
                     D1  D2 D3
                  D2  D3
        # Approach:
            Dynamic Programming
            opt[i][j]   i represents how many delivery are holding
                        j represents how many remaining delivery
                        output = opt[0][n]
                       
                                OPT[0][3]
                                3*OPT[1][2]
                        1*OPT[0][2]        2*OPT[2][1]
                        2*OPT[1][1]     2*OPT[1][1]  1*OPT[3][0]
                    1*OPT[0][1] 1*OPT[2][0]
                    
            OPT[i][j] = i*opt[i-1][j] + j*opt[i+1][j-1]
                                
        '''
        opt = [[0 for _ in range(n+1)] for _ in range(n+1)]

        for j in range(n+1):
            for i in range(n+1):
                if j == n:
                    opt[i][j] = j*opt[i+1][j-1]
                    return opt[0][n] % (pow(10, 9)+7)
                if i == 0 and j == 0:
                    continue
                if i == 0 and j == 1:
                    opt[i][j] = 1
                    continue
                if i == 1 and j == 0:
                    opt[i][j] = 1
                    continue
                if i == 0:
                    opt[i][j] = j*opt[i+1][j-1]
                elif j == 0:
                    opt[i][j] = i*opt[i-1][j]
                else:
                    if i + j > n:
                        break
                    opt[i][j] = i*opt[i-1][j] + j*opt[i+1][j-1]
                    
        
        #return opt[0][n] % (pow(10, 9)+7)
        


class Solution:
    def countOrders(self, n: int) -> int:
        orderResults = {}

        def orderHelper(pickupsLeft, heldPackages):
            key = (pickupsLeft, heldPackages)
            if key in orderResults:
                return orderResults[key]

            if key == (0, 0):
                return 0
            elif key == (0, 1):
                return 1
            elif key == (1, 0):
                return 1

            res = 0
            if pickupsLeft > 0:
                res += pickupsLeft * orderHelper(pickupsLeft - 1, heldPackages + 1)  # pickup an available package
            if heldPackages > 0:
                res += heldPackages * orderHelper(pickupsLeft, heldPackages - 1)  # deliver a held package
            res = res % (10**9 + 7)

            orderResults[key] = res
            return res

        return orderHelper(n, 0)

from itertools import permutations

class Solution:
    def countOrders(self, n: int) -> int:
        dp = {}
        MOD = 10**9 +7
        dp[(0,0)] = 1
        
        
        def helper(pick, deliver):
            nonlocal dp
            key = (pick, deliver)
            if key in dp:
                return dp[key]
            elif pick > deliver:
                return 0
            
            ans = 0
            if pick > 0:
                ans += helper(pick - 1, deliver) * pick %MOD
            if deliver > 0 and pick < deliver:
                ans += helper(pick, deliver - 1) * ( deliver-pick) %MOD
            dp[key] = ans
            return ans
        
        return helper(n,n)  %MOD
            
            
            
            


class Solution:
    def countOrders(self, n: int) -> int:
        MOD = int(1e9) + 7
        d = [[0] * (n + 2) for _ in range(n + 2)]
        d[0][0] = 1
        for i in range(n + 1):
            for j in range(i + 1):
                d[i + 1][j] = (d[i + 1][j]+ d[i][j] * (n - i))
                d[i][j + 1] = (d[i][j + 1] + d[i][j] * (i - j))
        return d[n][n - 1] % MOD



def oneMore(length: int) -> int:
    if length < 2:
        return 1
    return int((length * (length + 1))/2 + length + 1)

class Solution:
    def countOrders(self, n: int) -> int:
        acc = 1
        for i in range(0, n*2, 2):
            acc *= oneMore(i)
            acc %= int(1E9 + 7)
        return acc


class Solution:
    import sys
    
    def countOrders(self, n: int) -> int:
        
        print(sys.getrecursionlimit())
        #A = [0 for _ in range(n)]
        
        @lru_cache(None)
        def helper(p,d):
            #sys.setrecursionlimit(10**6)
            if(p == n and d == n):
                return 1
            ans = 0
            if(n>p):
                ans += (n-p)*(helper(p+1,d))
            if(p>d):
                ans += (p-d)*(helper(p,d+1))
            return ans
        
        return helper(0,0)%(10**9 + 7)

class Solution:
    def countOrders(self, n: int) -> int:
        # m = m * 2
        res = 1
        for i in range(1, n + 1):
            res = res * self.choose(2 * i, 2)
        return res % int(math.pow(10, 9) + 7)
    
    def choose(self, n, k):
        if 0 <= k <= n:
            ntok = 1
            ktok = 1
            for t in range(1, min(k, n - k) + 1):
                ntok *= n
                ktok *= t
                n -= 1
            return ntok // ktok
        else:
            return 0

class Solution:
    def countOrders(self, n: int) -> int:
        mod = 10 ** 9 + 7
        # return (2n)! / (2 ^ n)
        res = 1
        for i in range(2*n, 0, -1):
            res = res * i
            if i & 1:
                res /= 2
                res = res % mod
        return int(res)


class Solution:
    def countOrders(self, n: int) -> int:
        MOD = 10**9 + 7
        res = 1
        for i in range(2, n + 1):
            res = res * (2 * i - 1) * (2 * i) // 2 % MOD
        return res

class Solution:
    def countOrders(self, n: int) -> int:
        '''
Assume we have already n - 1 pairs, now we need to insert the nth pair.
To insert the first element, there are n * 2 - 1 chioces of position。
To insert the second element, there are n * 2 chioces of position。
So there are (n * 2 - 1) * n * 2 permutations.
Considering that delivery(i) is always after of pickup(i), we need to divide 2.
So it's (n * 2 - 1) * n.

        '''
        res=1
        for i in range(2,n+1):
            res=res*i*(2*i-1)
        return res%(10**9+7)

class Solution:
    def countOrders(self, n: int) -> int:
        res = 1
        for i in range(1, n+1):
            x = (i-1)*2+1
            possibilities = x*(x-1)//2+x
            res = (res * possibilities)%(1000000000 + 7)
        return res