import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	
	public static final BigInteger ZERO = BigInteger.ZERO;
	public static final BigInteger ONE = BigInteger.ONE;
	public static final BigInteger TWO = ONE.add(ONE);
	public static final BigInteger FIVE = TWO.multiply(TWO).add(ONE);
	public static final BigInteger SEVEN = FIVE.add(TWO);
	public static final BigInteger TEN = BigInteger.TEN;
	public static final BigInteger MOD = 
			TEN.multiply(TEN).multiply(TEN).multiply(TEN).multiply(TEN).multiply(TEN).multiply(TEN).multiply(TEN).multiply(TEN).add(SEVEN);
	
	public static final int zero = ZERO.intValue();
	public static final int one = ONE.intValue();
	public static final int two = TWO.intValue();
	
	public static BigInteger[][] mat_pow(BigInteger[][] mat, BigInteger pow){
		if(pow.equals(ONE)){
			return mat;
		}else if(pow.mod(TWO).equals(ZERO)){
			final BigInteger[][] ret = mat_pow(mat, pow.divide(TWO));
			return mat_mul(ret, ret);
		}else{
			return mat_mul(mat, mat_pow(mat, pow.subtract(ONE)));
		}
	}
	
	public static BigInteger[][] mat_mul(BigInteger[][] mat1, BigInteger[][] mat2){
		BigInteger[][] ret = new BigInteger[two][two];
		
		ret[zero][zero] = mat1[zero][zero].multiply(mat2[zero][zero]).add(mat1[zero][one].multiply(mat2[one][zero])).mod(MOD);
		ret[zero][one]  = mat1[zero][zero].multiply(mat2[zero][one]).add(mat1[zero][one].multiply(mat2[one][one])).mod(MOD);
		
		ret[one][zero] = mat1[one][zero].multiply(mat2[zero][zero]).add(mat1[one][one].multiply(mat2[one][zero])).mod(MOD);
		ret[one][one] = mat1[one][zero].multiply(mat2[zero][one]).add(mat1[one][one].multiply(mat2[one][one])).mod(MOD);
		
		return ret;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		BigInteger T = BigInteger.valueOf(sc.nextLong());
		while(T.compareTo(ZERO) != zero){ T = T.subtract(ONE);
			final BigInteger N = BigInteger.valueOf(sc.nextLong());
			
			if(N.equals(ZERO)){
				System.out.println(TWO);
			}else{
				final BigInteger[][] mat = {{ZERO, ONE}, {ONE, ONE}};
				final BigInteger[][] ret = mat_pow(mat, N);
				
				BigInteger answer = ret[zero][zero].multiply(TWO).add(ret[zero][one]).mod(MOD);
				System.out.println(answer);
			}
		}
	}
}