#include <iostream>
#include <math.h>
using namespace std;

void multiply(int F[2][2], int M[2][2]);
void power(int F[2][2], int n);

int fib(int n)
{
    n++;
    int F[2][2] = { {1, 1}, {1, 0} };
    if (n == 0)
        return 0;
    power(F, n - 1);

    return F[0][0];
}

void power(int F[2][2], int n)
{
    if (n == 0 || n == 1)
        return;
    int M[2][2] = { {1, 1}, {1, 0} };

    power(F, n / 2);
    multiply(F, F);

    if (n % 2 != 0)
        multiply(F, M);
}

void multiply(int F[2][2], int M[2][2])
{
    int num = 1000000007;
    int x = (F[0][0] * M[0][0] % num + F[0][1] * M[1][0] % num) % num;
    int y = (F[0][0] * M[0][1] % num + F[0][1] * M[1][1] % num) % num;
    int z = (F[1][0] * M[0][0] % num+ F[1][1] * M[1][0] % num) % num;
    int w = (F[1][0] * M[0][1] % num+ F[1][1] * M[1][1] % num) % num;

    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}

int main()
{
    int t;
    cin >> t;
    while (t > 0)
    {
        int n;
        cin >> n;

        cout << fib(n)<< endl;
        t--;
    }
}