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

    vector<__int128> fact;
    const int mod = 1e9 + 7;

    __int128 getPow(__int128 n, __int128 pow)
    {
        __int128 res = 1;

        while (pow != 0)
        {
            if (pow % 2 == 1)
            {
                res *= n;
                res %= ((int) 1e9 + 7);
            }
            n *= n;
            n %= ((int) 1e9 + 7);
            pow /= 2;
        }
        return res % ((int) 1e9 + 7);
    }

    void sieve(void)
    {
        fact.push_back(1);
        for (int i = 1; i < 1001; i++)
        {
            fact.push_back((i * fact[i - 1]) % mod);
        }
    }

    __int128 inverseMod(__int128 n)
    {
        return getPow(n, mod - 2);
    }
    int countOrders(int n) {
        
        if (n == 1)
            return 1;

        sieve();
        __int128 enu = fact[n * 2];
        __int128 den = inverseMod((getPow(2, n)) % mod);

        return (enu * den) % mod;
    }
};
9200