#include<bits/stdc++.h>

using namespace std;


long long dp[20000000];

long long fibo(long long ind){
    //cout<<ind<<endl;
    if(dp[ind]!=0)return dp[ind];
    if(ind==1||ind==2)return 1;
    else{
        dp[ind] = (fibo(ind-1)+fibo(ind-2))%((long long)1e8+7);
        return dp[ind];
    }
}

int main(){
    //ios_base::sync_with_stdio(0);
    long long t;
    cin>>t;
    while(t--){
        int n;
        scanf ("%d",&n);
        printf("%d \n",fibo(n));
    }
}