CQXYM is counting permutations length of 2n.

A permutation is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).

A permutation p(length of 2n) will be counted only if the number of i satisfying p_i<p_{i+1} is no less than n. For example:

  * Permutation [1, 2, 3, 4] will count, because the number of such i that p_i<p_{i+1} equals 3 (i = 1, i = 2, i = 3).
  * Permutation [3, 2, 1, 4] won't count, because the number of such i that p_i<p_{i+1} equals 1 (i = 3). 



CQXYM wants you to help him to count the number of such permutations modulo 1000000007 (10^9+7).

In addition, [modulo operation](https://en.wikipedia.org/wiki/Modulo_operation) is to get the remainder. For example:

  * 7 mod 3=1, because 7 = 3 ⋅ 2 + 1, 
  * 15 mod 4=3, because 15 = 4 ⋅ 3 + 3. 

Input

The input consists of multiple test cases. 

The first line contains an integer t (t ≥ 1) — the number of test cases. The description of the test cases follows.

Only one line of each test case contains an integer n(1 ≤ n ≤ 10^5).

It is guaranteed that the sum of n over all test cases does not exceed 10^5

Output

For each test case, print the answer in a single line.

Example

Input


4
1
2
9
91234


Output


1
12
830455698
890287984

Note

n=1, there is only one permutation that satisfies the condition: [1,2].

In permutation [1,2], p_1<p_2, and there is one i=1 satisfy the condition. Since 1 ≥ n, this permutation should be counted. In permutation [2,1], p_1>p_2. Because 0<n, this permutation should not be counted.

n=2, there are 12 permutations: [1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,2,3],[2,1,3,4],[2,3,1,4],[2,3,4,1],[2,4,1,3],[3,1,2,4],[3,4,1,2],[4,1,2,3].
/*
                       _oo0oo_
                      o8888888o
                      88" . "88
                      (| -_- |)
                      0\  =  /0
                    ___/`---'\___
                  .' \\|     |// '.
                 / \\|||  :  |||// \
                / _||||| -:- |||||- \
               |   | \\\  -  /// |   |
               | \_|  ''\---/''  |_/ |
               \  .-\__  '-'  ___/-. /
             ___'. .'  /--.--\  `. .'___
          ."" '<  `.___\_<|>_/___.' >' "".
         | | :  `- \`.;`\ _ /`;.`/ - ` : | |
         \  \ `_.   \_ __\ /__ _/   .-` /  /
     =====`-.____`.___ \_____/___.-`___.-'=====
                       `=---='
 
*/
import java.util.function.Consumer;
import java.util.*;
import java.math.*;
import java.io.*;
import java.lang.Math.*;

public class KickStart2020 {
	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		float nextFloat() {
			return Float.parseFloat(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}

	static long gcd(long a, long b) {
		if (b == 0)
			return a;
		return gcd(b, a % b);

	}

	static long lcm(long a, long b) {
		return a / gcd(a, b) * b;
	}

	public static class Pair implements Comparable<Pair> {
		public int index;
		public int value;

		public Pair(int index, int value) {
			this.index = index;
			this.value = value;
		}

		@Override
		public int compareTo(Pair other) {
			// multiplied to -1 as the author need descending sort order
			if(other.value < this.value) return -1;
			else if(other.value > this.value) return 1;
			else return 0;
		}
		@Override
		public String toString() {
			return this.index + " " + this.value;
		}
	}
	static class Trio{
		int key;
		int value;
		int x;
		Trio(int a, int b, int c){
			this.key = a;
			this.value = b;
			this.x = c;
		}
		@Override
		public String toString() {
			return this.key + " " + this.value + " " + this.x;
		}
	}
	static boolean isPrime(long d) {
		if (d == 1)
			return false;
		for (int i = 2; i <= (long) Math.sqrt(d); i++) {
			if (d % i == 0)
				return false;
		}
		return true;
	}

	static String decimalTob(long n, int k, String s) {
          long x = n % k;
          long y = n / k;
          s = x + "" + s;
          if(y > 0) {
        	  s = decimalTob(y, k, s);
          }
          return s;
	}

	static long powermod(long x, long y, long mod) {
		long ans = 1;
		x = x % mod;
		if (x == 0)
			return 0;
		int i = 1;
		while (y > 0) {
			if ((y & 1) != 0)
				ans = (ans * x) % mod;
			y = y >> 1;
			x = (x * x) % mod;
		}
		return ans;
	}

	static int computeXOR(int n) {
		if (n % 4 == 0)
			return n;
		if (n % 4 == 1)
			return 1;
		if (n % 4 == 2)
			return n + 1;
		return 0;
	}
	 static boolean isPrime(int n) {
		 if(n == 1) return true;
		 for(int i = 2; i * i <= n; i++) if(n % i == 0) return false;
        return true;
	 }
	public static void main(String[] args) throws Exception {
		FastReader sc = new FastReader();
		PrintWriter out = new PrintWriter(System.out);
		int t = sc.nextInt();
		outerloop: while (t-- > 0) {
          int mod = (int)(1e9 + 7);
          int n = sc.nextInt();
          long ans = 1;
          for(int i = 3; i <= 2 * n; i++) {
        	  ans = (ans * i) % mod;
          }
          out.println(ans);
			}
		out.close();
	}
}