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[][] mat_X, BigInteger[][] mat_Y){ BigInteger[][] ret = new BigInteger[two][two]; ret[zero][zero] = mat_X[zero][zero].multiply(mat_Y[zero][zero]).add(mat_X[zero][one].multiply(mat_Y[one][zero])).mod(MOD); ret[zero][one] = mat_X[zero][zero].multiply(mat_Y[zero][one]).add(mat_X[zero][one].multiply(mat_Y[one][one])).mod(MOD); ret[one][zero] = mat_X[one][zero].multiply(mat_Y[zero][zero]).add(mat_X[one][one].multiply(mat_Y[one][zero])).mod(MOD); ret[one][one] = mat_X[one][zero].multiply(mat_Y[zero][one]).add(mat_X[one][one].multiply(mat_Y[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); } } } }