package competitive;
import java.math.BigInteger;
import java.util.Scanner;
public class FastFIBONACCI {
static int mod = 10000007;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
long n = sc.nextLong();
System.out.println(fab(n));
}
}
public static BigInteger fab(long n) {
long t[][] = new long[2][2];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
if (i < 1) {
if (j == i + 1) {
t[i][j] = 1;
} else {
continue;
}
}
t[i][j] = 1;
}
}
t = power(t, n - 1);
long f1[] = { 1, 1 };
BigInteger ans = new BigInteger("0");
for(int i = 0; i < 2; i++) {
//long k = (t[0][i] * f1[i]) % mod;
ans = ans.add(BigInteger.valueOf((t[0][i] * f1[i]) % mod));
}
return ans;
}
public static long[][] power(long arr[][], long b) {
if (b == 1 || b == 0) {
return arr;
}
if ((b & 1) != 0) {
return mutiply(arr, power(arr, b - 1));
} else {
long s[][] = power(arr, b / 2);
return mutiply(s, s);
}
}
public static long[][] mutiply(long[][] t, long[][] power) {
// TODO Auto-generated method stub
long ans[][] = new long[t.length][t.length];
for (int i = 0; i < t.length; i++) {
for (int j = 0; j < t.length; j++) {
for (int x = 0; x < t.length; x++) {
ans[i][j] = ((ans[i][j] + ((t[i][x] * power[x][j]) % mod)) % mod);
}
}
}
return ans;
}
}