#include <cstdio>

#include <iostream>

#include<cstring>

using namespace std;

const long long MOD = 1e9+;

long long mod1(char *a1,int b)

{

    long long  a[] = {};

    long long c[] = {};

    long long  i, k, d;

    k = strlen(a1);

    for(i = ; i < k; i++)  a[i] = a1[k - i - ] - '';

    d = ;

    for(i = k - ; i >=  ; i--)

    {

        d = d *  + a[i];

        c[i] = d / b;

        d = d % b;

    }

    while(c[k - ] ==  && k > )  k--;

    return d;

}

struct matrix

{

    long long m[][];

}ans, base;

matrix multi(matrix a, matrix b)

{

    matrix tmp;

    for(int i = ; i < ; ++i)

    {

        for(int j = ; j < ; ++j)

        {

            tmp.m[i][j] = ;

            for(int k = ; k < ; ++k)

                tmp.m[i][j] = (tmp.m[i][j] + a.m[i][k] * b.m[k][j]% MOD) % MOD;

        }

    }

    return tmp;

}

int fast_mod(int n)  // 求矩阵 base 的  n 次幂

{

    base.m[][] = base.m[][] = base.m[][] = ;

    base.m[][] = ;

    ans.m[][] = ans.m[][] = ;  // ans 初始化为单位矩阵

    ans.m[][] = ans.m[][] = ;

    while(n)

    {

        if(n & )

        {

            ans = multi(ans, base);

        }

        base = multi(base, base);

        n >>= ;

    }

    return ans.m[][];

}

char SS[];

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%s",SS);

        //printf("%d\n",mod1(SS,2000000016));

        printf("%lld\n", fast_mod(mod1(SS,))%MOD);

    }

    return ;

}