import java.io.*;
import java.util.Arrays;

public class TruthsBottomUp {    
    static long MOD = 1_000_000_007;

    static int FALSE = 0, TRUE = 1, PAREN = 2, NOT = 3, AND = 4, OR = 5;
    static int[] OPS = {FALSE, TRUE, PAREN, NOT, AND, OR};
    static int[] VALUES = {FALSE, TRUE};

    static int[] VALID_LEFT_AND_OPS = {FALSE, TRUE, PAREN, NOT};
    static int[] VALID_RIGHT_AND_OPS = {FALSE, TRUE, PAREN, NOT, AND};
    static int[] VALID_LEFT_OR_OPS = {FALSE, TRUE, PAREN, NOT, AND};
    static int[] VALID_RIGHT_OR_OPS = {FALSE, TRUE, PAREN, NOT, AND, OR};

    static int[][] AND_TRUE_VALUES = {{TRUE, TRUE}};
    static int[][] AND_FALSE_VALUES = {{FALSE, FALSE}, {FALSE, TRUE}, {TRUE, FALSE}};
    static int[][] OR_TRUE_VALUES = {{FALSE, TRUE}, {TRUE, FALSE}, {TRUE, TRUE}};
    static int[][] OR_FALSE_VALUES = {{FALSE, FALSE}};
    
    static int[][][] count = new int[301][2][6]; // [symbols][value][lastOp]
    
    static {
        count[1][TRUE][TRUE] = 1;
        count[1][FALSE][FALSE] = 1;
        for (int symbols = 2; symbols <= 300; symbols++) {
            for (int value : VALUES) {
                long parenTotal = 0;
                for (int op : OPS) {
                    parenTotal += count[symbols - 2][value][op];
                }
                count[symbols][value][PAREN] = (int) (parenTotal % MOD);
                
                int inverse = value == TRUE ? FALSE : TRUE;
                long notTotal = 0;
                for (int op = 0; op < 4; op++) {
                    notTotal += count[symbols - 1][inverse][op];
                }
                count[symbols][value][NOT] = (int) (notTotal % MOD);
                
                int[][] andValidValues = value == TRUE ? AND_TRUE_VALUES : AND_FALSE_VALUES;
                long andTotal = 0;
                for (int[] values : andValidValues) {
                    int leftValue = values[0], rightValue = values[1];
                    for (int opPosition = 1; opPosition < symbols - 1; opPosition++) {
                        long leftTotal = 0;
                        for (int op : VALID_LEFT_AND_OPS) {
                            leftTotal += count[opPosition][leftValue][op];
                        }
                        long rightTotal = 0;
                        for (int op : VALID_RIGHT_AND_OPS) {
                            rightTotal += count[symbols - opPosition - 1][rightValue][op];
                        }
                        andTotal += (((leftTotal % MOD) * (rightTotal % MOD)) % MOD);
                    }
                }
                count[symbols][value][AND] = (int) (andTotal % ((long) MOD));
                
                int[][] orValidValues = value == TRUE ? OR_TRUE_VALUES : OR_FALSE_VALUES;
                long orTotal = 0;
                for (int[] values : orValidValues) {
                    int leftValue = values[0], rightValue = values[1];
                    for (int opPosition = 1; opPosition < symbols - 1; opPosition++) {
                        long leftTotal = 0;
                        for (int op : VALID_LEFT_OR_OPS) {
                            leftTotal += count[opPosition][leftValue][op];
                        }
                        long rightTotal = 0;
                        for (int op : VALID_RIGHT_OR_OPS) {
                            rightTotal += count[symbols - opPosition - 1][rightValue][op];
                        }
                        orTotal += (((leftTotal % MOD) * (rightTotal % MOD)) % MOD);
                    }
                }
                count[symbols][value][OR] = (int) (orTotal % ((long) MOD));
            }
        }
    }
    
    /**
     * Count and return the number of true boolean expressions that use exactly N
     * symbols modulo 1000000007.
     * 
     * N: the number of symbols in the boolean expression
     */
    static int solve(int N) {
        long total = 0;
        for (int op : OPS) {
            total += count[N][TRUE][op];
        }
        return (int) (total % ((long) MOD));
    }
    
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(in.readLine());
        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(in.readLine());
            out.println(solve(N));
        }
        out.flush();
    }
}