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].
// Generated by Code Flattener.
// https://plugins.jetbrains.com/plugin/9979-idea-code-flattener

import java.io.*;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        Solution solution = new ASolution();
        boolean local = System.getProperty("ONLINE_JUDGE") == null && !solution.isInteractive();
        String input = local ? "input.txt" : null;
        solution.in = new MyScanner(input);
        solution.out = MyWriter.of(null);
        solution.bm = new Benchmark();
        solution.al = new Algorithm();
        solution.run();
        solution.close();
    }

    private abstract static class Solution {
        public MyScanner in;
        public MyWriter out;
        public Benchmark bm;
        public Algorithm al;

        public void init() {
        }

        public abstract void solve();

        protected boolean isMultiTest() {
            return true;
        }

        public void run() {
            init();
            if (isMultiTest()) {
                int t = in.nextInt();
                for (int i = 0; i < t; i++) {
                    solve();
                }
            } else {
                solve();
            }
        }

        public void close() {
            out.close();
        }

        public boolean isInteractive() {
            return false;
        }
    }

    private static class ASolution extends Solution {
        ModInt[] fact;

        @Override
        public void init() {
            fact = new ModInt[200010];
            fact[0] = ModInt.ONE;
            for (int i = 1; i < fact.length; i++) {
                fact[i] = fact[i - 1].multiply(new ModInt(i));
            }
        }

        public void solve() {
            int n = in.nextInt();
            System.out.println(fact[2 * n].divide(new ModInt(2)).intValue());
        }
    }

    private static class MyScanner {
        private final BufferedReader br;
        private StringTokenizer st;

        public MyScanner(String fileName) {
            if (fileName != null) {
                try {
                    File file = new File(getClass().getClassLoader().getResource(fileName).getFile());
                    br = new BufferedReader(new FileReader(file));
                } catch (FileNotFoundException e) {
                    throw new RuntimeException(e);
                }
            } else {
                br = new BufferedReader(new InputStreamReader(System.in));
            }
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                st = new StringTokenizer(nextLine());
            }
            return st.nextToken();
        }

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

        public String nextLine() {
            try {
                String line = br.readLine();
                if (line == null) {
                    throw new RuntimeException("empty line");
                }
                st = null;
                return line;
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
    }

    private static class Benchmark {
    }

    private static class Algorithm {
    }

    private static class MyWriter extends PrintWriter {
        public static MyWriter of(String fileName) {
            if (fileName != null) {
                try {
                    return new MyWriter(new FileWriter(fileName));
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            } else {
                return new MyWriter(new BufferedOutputStream(System.out));
            }
        }

        public MyWriter(Writer writer) {
            super(writer);
        }

        public MyWriter(OutputStream out) {
            super(out);
        }
    }

    private static class ModInt {
        private static final int MOD = 1000000007;
        public static final ModInt ONE = new ModInt(1);
        private static final Map<ModInt, ModInt> inverseCache = new HashMap<>();
        private final int value;

        public ModInt(int value) {
            if (value < 0) {
                throw new IllegalArgumentException();
            }
            this.value = value;
        }

        public ModInt multiply(ModInt other) {
            return new ModInt((int) (((long) this.value * other.value) % MOD));
        }

        public ModInt pow(int degree) {
            if (degree == 0) {
                return ModInt.ONE;
            }
            if (degree % 2 == 1) {
                return this.multiply(pow(degree - 1));
            }
            ModInt tmp = this.pow(degree / 2);
            return tmp.multiply(tmp);
        }

        public ModInt inverse() {
            ModInt tmp = inverseCache.get(this);
            if (tmp == null) {
                tmp = this.pow(MOD - 2);
                inverseCache.put(this, tmp);
            }
            return tmp;
        }

        public ModInt divide(ModInt other) {
            return this.multiply(other.inverse());
        }

        public int intValue() {
            return value;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            ModInt modInt = (ModInt) o;
            return value == modInt.value;
        }

        @Override
        public int hashCode() {
            return Objects.hash(value);
        }
    }
}