#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define fi first
#define se second
#define Mp make_pair
using namespace std;
typedef long long ll;
int rd() {
	int r=0; bool w=false; char ch=getchar();
	while( ch < '0' || ch > '9' ) w = !(ch^45), ch = getchar();
	while( ch >= '0' && ch <= '9' ) r = (r<<1) + (r<<3) + (ch^48), ch = getchar();
	return w ? -r : r;
}

#define MAXL 10000
const int mod = 1e9+7;
const int ft[3][3] = {
	{1,1,1},
	{1,4,2},
	{1,2,4}
}, gt[3][3] = {
	{1,1,1},
	{2,1,4},
	{3,6,5}
};
void add( int &a , int b ) { a = (a + b) % mod; a = (a + mod)%mod; }
int quick_pow( int a , int p , int m ) {
	if( m == 7 ) p %= 6;
	int ret = 1;
	for(;p;p>>=1) {
		if( p&1 ) ret = 1ll * ret * a % m;
		a = a * a % m;
	}
	return ret;
}

int n;
int f[MAXL+5][7][7][7], g[MAXL+5][7][7][7];
int sf[MAXL+5], sf1[MAXL+5][3][7], sf2[MAXL+5][3][7][7];
char s[MAXL+5];
int a[7];
int mod7( int x ) { return (x%7+7)%7; }
int dfs( int len ) {
	if( len == 0 ) return 0;
	int ret = 0;
	if( s[len] == '1' ) {
		int lenf = len / 2, leng = (len - 1) / 2;
//		FOR(i1,0,6) FOR(j1,0,6) FOR(k1,0,6) FOR(i2,0,6) FOR(j2,0,6) FOR(k2,0,6) if( f[lenf][i1][j1][k1] && g[leng][i2][j2][k2] ) {
//			if( (i1 + i2 + a[1]) % 7 == 0 || (j1 + j2 + a[2]) % 7 == 0 || (k1 + k2 + a[3]) % 7 == 0 ||
//				(i1 - i2 + a[6] + 7) % 7 == 0 || (j1 - j2 + a[5] + 7) % 7 == 0 || (k1 - k2 + a[4] + 7) % 7 == 0 ) continue;
//			ret = (ret + 1ll * f[lenf][i1][j1][k1] * g[leng][i2][j2][k2]) % mod;
//		}
		FOR(i2,0,6) FOR(j2,0,6) FOR(k2,0,6) {
			int now =  sf[lenf];
			int i[3] = {1,mod7(-a[1]-i2)}, j[3] = {1,mod7(-a[2]-j2)}, k[3] = {1,mod7(-a[3]-k2)};
			if( mod7(-a[1]-i2) != mod7(-a[6]+i2) ) i[++i[0]] = mod7(-a[6]+i2);
			if( mod7(-a[2]-j2) != mod7(-a[5]+j2) ) j[++j[0]] = mod7(-a[5]+j2);
			if( mod7(-a[3]-k2) != mod7(-a[4]+k2) ) k[++k[0]] = mod7(-a[4]+k2);
			FOR(d,1,i[0]) add( now , -sf1[lenf][0][i[d]] );
			FOR(d,1,j[0]) add( now , -sf1[lenf][1][j[d]] );
			FOR(d,1,k[0]) add( now , -sf1[lenf][2][k[d]] );
			FOR(d1,1,i[0]) FOR(d2,1,j[0]) add( now , sf2[lenf][0][i[d1]][j[d2]] );
			FOR(d1,1,i[0]) FOR(d2,1,k[0]) add( now , sf2[lenf][1][i[d1]][k[d2]] );
			FOR(d1,1,j[0]) FOR(d2,1,k[0]) add( now , sf2[lenf][2][j[d1]][k[d2]] );
			FOR(d1,1,i[0]) FOR(d2,1,j[0]) FOR(d3,1,k[0]) add( now , -f[lenf][i[d1]][j[d2]][k[d3]]);
			add( ret , 1ll * now * g[leng][i2][j2][k2] % mod );
		}
		FOR(i,1,6) a[i] = (a[i] + quick_pow(i,len-1,7)) % 7;
	}
	return (ret + dfs(len-1)) % mod;
}
void solve() {
	scanf("%s",s+1); n = strlen(s+1); reverse(s+1,s+1+n);
    int c = 1; FOR(i,1,n) {
    	int e = (s[i] - '0') ^ c;
    	c = (s[i] - '0') & c; s[i] = '0' + e;
	} if( c ) s[++n] = '1';
	
	memset(a,0,sizeof(a));
	int tmp = dfs(n);
	printf("%d\n",(tmp%mod+mod)%mod);
	return;
}


int main() {
//	freopen("test.txt","r",stdin);
	f[1][1][1][1] = g[0][0][0][0] = 1;
	
	FOR(j,0,6) FOR(k,0,6) FOR(l,0,6)
		add( sf[1] , f[1][j][k][l] ),
		add( sf2[1][0][j][k] , f[1][j][k][l] ),
		add( sf2[1][1][j][l] , f[1][j][k][l] ),
		add( sf2[1][2][k][l] , f[1][j][k][l] ),
		add( sf1[1][0][j] , f[1][j][k][l] ),
		add( sf1[1][1][k] , f[1][j][k][l] ),
		add( sf1[1][2][l] , f[1][j][k][l] );
	FOR(i,2,MAXL) {
		FOR(j,0,6) FOR(k,0,6) FOR(l,0,6)
			f[i][j][k][l] = (f[i-1][j][k][l] + f[i-1][(j-ft[0][(i-1)%3]+7)%7][(k-ft[1][(i-1)%3]+7)%7][(l-ft[2][(i-1)%3]+7)%7]) % mod,
			add( sf[i] , f[i][j][k][l] ),
			add( sf2[i][0][j][k] , f[i][j][k][l] ),
			add( sf2[i][1][j][l] , f[i][j][k][l] ),
			add( sf2[i][2][k][l] , f[i][j][k][l] ),
			add( sf1[i][0][j] , f[i][j][k][l] ),
			add( sf1[i][1][k] , f[i][j][k][l] ),
			add( sf1[i][2][l] , f[i][j][k][l] );
	}
	FOR(i,1,MAXL)
		FOR(j,0,6) FOR(k,0,6) FOR(l,0,6)
			g[i][j][k][l] = (g[i-1][j][k][l] + g[i-1][(j-gt[0][(i-1)%3]+7)%7][(k-gt[1][(i-1)%3]+7)%7][(l-gt[2][(i-1)%3]+7)%7]) % mod;
	int t = rd(); while( t-- ) solve();
	return 0;
}