// 본 문제를 피보나치 수열로 풀었습니다.

#include <stdio.h>
#include <stdlib.h>

int A[120][51];       // 만들수 잇는 블록의 경우를 더해감
int common[120][51];  // 대칭되는 블록의 경우를 계산
int sol[120][51];  // 만들수있는 경우와 대칭되는 경우를 뺌.
int in[60];    // 입력으로 받는 타일 n을 받는 배열
__int64  sum;  // 문자열로 나눗셈을 하기위해 쓴 변수

int main()
{
int C,i,j,s,max,t;  //C는 받아들이는 경우의 수 C


    scanf("%d",&C);

    for(i=1;i<=C;i++)scanf("%d",&in[i]);

common[1][50] = 1;
common[1][0] = 1;
common[2][50] = 2;
common[2][0] = 1;
common[3][50] = 1;
common[3][0] = 1;
common[4][50] = 3;
common[4][0] = 1;

A[1][50] = 1;
A[2][50] = 2;
A[1][0] = 1;
A[2][0] = 1;

for(i=1;i<=50;i++)  //좌우대칭타일 홀수부의 피보나치 수열
{
    if(common[2*i+1][0]>common[2*i-1][0])
    s = common[2*i+1][0];
    else s = common[2*i-1][0];
    for(j=50;50-s<j;j--)
    {
        common[2*i+3][j] =common[2*i+3][j]+common[2*i+1][j] + common[2*i-1][j];
        if(common[2*i+3][j]>=10)
        {
            common[2*i+3][j]= common[2*i+3][j]-10;
            common[2*i+3][j-1]+=1;
            if(j-1==50-s) j--;
        }   
    }
    common[2*i+3][0] = 50-j;

    if(common[2*i+2][0]>common[2*i][0])
    s = common[2*i+2][0];
    else s = common[2*i][0];

    for(j=50;50-s<j;j--) //좌우대칭타일 짝수부의피보나치 수열
    {
        common[2*i+4][j] =common[2*i+4][j] + common[2*i+2][j] + common[2*i][j];
        if(common[2*i+4][j]>=10)
        {
            common[2*i+4][j]= common[2*i+4][j]-10;
            common[2*i+4][j-1]+=1;
            if(j-1==50-s) j--;
        }   
    }
    common[2*i+4][0] = 50-j;    
}


for(i=3;i<=100;i++)  //총 만들수있는 타일의 경우의 수 계산
{
    if(A[i-1][0]>A[i-2][0])
        s = A[i-1][0];
    else s = A[i-2][0];

    for(j=50;50-s<j;j--)
    {
        A[i][j] = A[i][j] + A[i-1][j]+A[i-2][j];
        if(A[i][j]>=10)
        {
            A[i][j] = A[i][j] -10;
            A[i][j-1]+=1;
            if(j-1==50-s) j--;
        }
    }
    A[i][0] = 50-j;
}

for(i=1;i<=C;i++)
{              // 총 경우의 수와 대칭타일의 수를 뺌. 
    t = in[i];
    for(j=50;50-A[t][0]<j;j--)
    {
    if(A[t][j]>=common[t][j])
        sol[t][j] = A[t][j]-common[t][j];

    else
    {
        A[t][j-1]-=1;
        A[t][j] +=10;
        sol[t][j] = A[t][j]-common[t][j];
    }
    }

    max=0;             
    for(j=50;j>0;j--)  //빼고나서 sol의 숫자길이를 측정. 
    {
    if(sol[t][j]!=0) max=j;
    }
    if(max!=0)
    sol[t][0] = 50-max+1;

    sum=0;
    for(j=50-sol[t][0]+1;j<=50;j++) 
    //1000000007로 나눈 나머지를 구함
    {
        sum+=sol[t][j];
        if(sum>=1000000007)
        {
            sum=sum%1000000007;
            if(j!=50)
            sum=sum*10;
        }
        else
        {
            if(j!=50)
            sum = sum*10;
        }

    }
    printf("%d\n",sum); //출력 
}




return 0;

}