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].
import java.io.*;
import java.util.*;

/**
 * Made by egor https://github.com/chermehdi/egor.
 *
 * @author Azuz 
 *
 */
public class Main {
  private static final long MOD = (long) 1e9 + 7;
  private static final int MAXN = (int) 2e5 + 5;
  private static final long[] fact = new long[MAXN];
  private static final long inv = 500000004;
  static {
    fact[0] = 1;
    for (int i = 1; i < MAXN; ++i) {
      fact[i] = (fact[i - 1] * i) % MOD;
    }
  }

  void solve(int testNumber, InputReader in, PrintWriter out) {
    int n = in.nextInt();
    out.println((fact[n + n] * inv) % MOD);
  }

  void solve(InputReader in, PrintWriter out) {
    int current = 0;
    int tests = in.nextInt();
    while (current < tests) {
      solve(++current, in, out);
    }
  }


  public static void main(String[] args) {
    InputReader in = new InputReader(System.in);
    try (PrintWriter out = new PrintWriter(System.out)) {
      new Main().solve(in, out);
    }
  }
}

class InputReader  {

  private InputStream stream;
  private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
  private static final int EOF = -1;
  private byte[] buf = new byte[DEFAULT_BUFFER_SIZE];
  private int curChar;
  private int numChars;

  public InputReader(InputStream stream) {
    this.stream = stream;
  }

  public int[] readIntArray(int tokens) {
    int[] ret = new int[tokens];
    for (int i = 0; i < tokens; i++) {
      ret[i] = nextInt();
    }
    return ret;
  }

  public int read() {
    if (this.numChars == EOF) {
      throw new UnknownError();
    } else {
      if (this.curChar >= this.numChars) {
        this.curChar = 0;

        try {
          this.numChars = this.stream.read(this.buf);
        } catch (IOException ex) {
          throw new InputMismatchException();
        }

        if (this.numChars <= 0) {
          return EOF;
        }
      }

      return this.buf[this.curChar++];
    }
  }

  public int nextInt() {
    int c;
    for (c = this.read(); isSpaceChar(c); c = this.read()) {
    }

    byte sgn = 1;
    if (c == 45) {
      sgn = -1;
      c = this.read();
    }

    int res = 0;

    while (c >= 48 && c <= 57) {
      res *= 10;
      res += c - 48;
      c = this.read();
      if (isSpaceChar(c)) {
        return res * sgn;
      }
    }

    throw new InputMismatchException();
  }

  public long nextLong() {
    int c;
    for (c = this.read(); isSpaceChar(c); c = this.read()) {
    }

    byte sgn = 1;
    if (c == 45) {
      sgn = -1;
      c = this.read();
    }

    long res = 0;

    while (c >= 48 && c <= 57) {
      res *= 10L;
      res += c - 48;
      c = this.read();
      if (isSpaceChar(c)) {
        return res * sgn;
      }
    }
    throw new InputMismatchException();
  }

  public double nextDouble() {
    double ret = 0, div = 1;
    int c = read();
    while (c <= ' ') {
      c = read();
    }
    boolean neg = (c == '-');
    if (neg) {
      c = read();
    }

    do {
      ret = ret * 10 + c - '0';
    }
    while ((c = read()) >= '0' && c <= '9');

    if (c == '.') {
      while ((c = read()) >= '0' && c <= '9') {
        ret += (c - '0') / (div *= 10);
      }
    }

    if (neg) {
      return -ret;
    }
    return ret;
  }

  public String next() {
    int c;
    while (isSpaceChar(c = this.read())) {
    }

    StringBuilder result = new StringBuilder();
    result.appendCodePoint(c);

    while (!isSpaceChar(c = this.read())) {
      result.appendCodePoint(c);
    }

    return result.toString();
  }

  public String nextLine() {
    int c;
    StringBuilder result = new StringBuilder();
    boolean read = false;
    while ((c = this.read()) != '\n') {
      if (c == -1) {
        return null;
      }
      result.appendCodePoint(c);
      read = true;
    }
    if (!read) {
      return null;
    }
    return result.toString();
  }

  public static boolean isSpaceChar(int c) {
    return c == 32 || c == 10 || c == 13 || c == 9 || c == EOF;
  }

  public int[] nextIntArray(int n) {
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = nextInt();
    }
    return arr;
  }

  public long[] nextLongArray(int n) {
    long[] arr = new long[n];
    for (int i = 0; i < n; i++) {
      arr[i] = nextLong();
    }
    return arr;
  }

  public int[][] nextIntMatrix(int n, int m) {
    int[][] arr = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        arr[i][j] = nextInt();
      }
    }
    return arr;
  }

  public long[][] nextLongMatrix(int n, int m) {
    long[][] arr = new long[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        arr[i][j] = nextLong();
      }
    }
    return arr;
  }

  public char[] nextCharArray() {
    return next().toCharArray();
  }

  public double[] nextDoubleArray(int n) {
    double[] ret = new double[n];
    for (int i = 0; i < n; i++) {
      ret[i] = nextDouble();
    }
    return ret;
  }

  public int[]
  nextIntArrayOneBased(int n) {
    int[] ret = new int[n + 1];
    for (int i = 1; i <= n; i++) {
      ret[i] = nextInt();
    }
    return ret;
  }

  public char[][] nextCharMatrix(int n, int m) {
    char[][] res = new char[n][m];
    for (int i = 0; i < n; ++i) {
      res[i] = nextCharArray();
    }
    return res;
  }
}
