*Author:* yashu2040

*Tester:* pulkit_0110

*Editorialist:* yashu2040

# DIFFICULTY:

MEDIUM.

#EXPLANATION

The key idea is that for any n, you can select the pair having colour n and place the pair in any position such that left parentheses occurs before right parentheses and these position can be calculated in 2nC2 ways.

Now you are left with (n-1) pairs, apply the same logic to remaining pairs.

You can precalculate the answer of each n <= 1e5 and each query can be solved in O(1) time complexity.

Here’s the code :

## Setter's Solution

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main(){

ios_base::sync_with_stdio(false);

cin.tie(NULL);

cout.tie(NULL);

ll mod = 1000000007;

ll dp[100000+1];

dp[1] = 1;

dp[2] = 6;

for(int i=3; i<=100000; i++) {

dp[i] = ((dp[i-1]*(2*i-1)%mod)*i)%mod;

}

int t = 1;

cin>>t;

while(t–){

int n;

cin>>n;

cout<<dp[n]<<"\n";

}

}