/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time 
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const int INF=1e18;
typedef unsigned long long ull;
typedef __int128 lll;
struct Fastmod
{
	int m;int b;
	void init(int _m){m=_m;b=((lll)1<<64)/m;}
	int operator()(ull a)
	{
		int q=((lll)a*b)>>64,r=a-q*m;
		if(r>=m) r-=m;
		return r;
	}
}Mod;
int mul(int a,int b){
	return Mod(a*b);
}
int wei[7][10005];
int fe[5005][7][7][7],se[5005][8][8][8],fo[5005][7][7][7],so[5005][8][8][8];
void add(int &x,int y)
{
	x+=y;
	if(x>=mod) x-=mod;
}
int pw2[10005];
void solve()
{
	string s;
	cin>>s;
	int n=s.size();
	int ans=0;
	int r1=0,r2=0,r3=0,r4=0,r5=0,r6=0;
	for(int lcp=0;lcp<=s.size();lcp++) 
	{
		if(lcp==s.size())
		{
			if(r1!=0&&r2!=0&&r3!=0&&r4!=0&&r5!=0&&r6!=0&&s[s.size()-1]=='1') ans=(ans+1)%mod;
			break;
		}
		if(s[lcp]=='1'&&lcp+1!=s.size()) 
		{
			for(int re1=0;re1<7;re1++) for(int re2=0;re2<7;re2++) for(int re3=0;re3<7;re3++) if(se[(n-lcp)/2][re1][re2][re3]) 
			{
				vector <int> c1,c2,c3;
				c1.pb(7),c2.pb(7),c3.pb(7);
				int ban3=(r4+re3)%7,ban2=(r5+re2)%7,ban1=(r6+re1)%7;
				c1.pb(ban1),c2.pb(ban2),c3.pb(ban3);
				if((14-r1-re1)%7!=ban1) c1.pb((14-r1-re1)%7);
				if((14-r2-re2)%7!=ban2) c2.pb((14-r2-re2)%7);
				if((14-r3-re3)%7!=ban3) c3.pb((14-r3-re3)%7);
				int re=n-lcp-1;
				for(int x=0;x<c1.size();x++) for(int y=0;y<c2.size();y++) for(int z=0;z<c3.size();z++)
				{
					int coef=mul(se[(re+1)/2][re1][re2][re3],so[re/2][c1[x]][c2[y]][c3[z]]);
					if(((x!=0)+(y!=0)+(z!=0))%2==0) 
					{
						ans+=coef;
						if(ans>=mod) ans-=mod;
					}
					else 
					{
						ans-=coef;
						if(ans<0) ans+=mod;
					}
				}
			}
		}
		r1=(r1+wei[1][n-lcp-1]*(s[lcp]-'0'))%7;
		r2=(r2+wei[2][n-lcp-1]*(s[lcp]-'0'))%7;
		r3=(r3+wei[3][n-lcp-1]*(s[lcp]-'0'))%7;
		r4=(r4+wei[4][n-lcp-1]*(s[lcp]-'0'))%7;
		r5=(r5+wei[5][n-lcp-1]*(s[lcp]-'0'))%7;
		r6=(r6+wei[6][n-lcp-1]*(s[lcp]-'0'))%7;
	}
	cout<<ans<<"\n";
	
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	for(int i=1;i<=6;i++)
	{
		for(int j=0,w=1;j<10005;j++) wei[i][j]=w,w=w*i%7;
	}
	pw2[0]=1;
	for(int i=1;i<10005;i++) pw2[i]=2LL*pw2[i-1]%mod;
	fe[0][0][0][0]=1;
	for(int i=0;i<=5000;i++)
	{
		for(int r1=0;r1<7;r1++) for(int r2=0;r2<7;r2++) for(int r3=0;r3<7;r3++) for(int d=0;d<2;d++)
		{
			if(i==0&&d==0) continue;
			add(fe[i+1][(r1+d*wei[1][i*2])%7][(r2+d*wei[2][i*2])%7][(r3+d*wei[3][i*2])%7],fe[i][r1][r2][r3]);
		}
	}
	for(int i=0;i<=5000;i++)
	{
		for(int x=0;x<7;x++) for(int y=0;y<7;y++) for(int z=0;z<7;z++)
		{
			add(se[i][x][y][z],fe[i][x][y][z]),add(se[i][7][y][z],fe[i][x][y][z]),add(se[i][x][7][z],fe[i][x][y][z]),add(se[i][x][y][7],fe[i][x][y][z]);
			add(se[i][7][7][z],fe[i][x][y][z]),add(se[i][7][y][7],fe[i][x][y][z]),add(se[i][x][7][7],fe[i][x][y][z]),add(se[i][7][7][7],fe[i][x][y][z]);
		}
	}
	
	fo[0][0][0][0]=1;
	for(int i=0;i<=5000;i++)
	{
		for(int r1=0;r1<7;r1++) for(int r2=0;r2<7;r2++) for(int r3=0;r3<7;r3++) for(int d=0;d<2;d++)
		{
			add(fo[i+1][(r1+d*wei[1][i*2+1])%7][(r2+d*wei[2][i*2+1])%7][(r3+d*wei[3][i*2+1])%7],fo[i][r1][r2][r3]);
		}
	}
	for(int i=0;i<=5000;i++)
	{
		for(int x=0;x<7;x++) for(int y=0;y<7;y++) for(int z=0;z<7;z++)
		{
			add(so[i][x][y][z],fo[i][x][y][z]),add(so[i][7][y][z],fo[i][x][y][z]),add(so[i][x][7][z],fo[i][x][y][z]),add(so[i][x][y][7],fo[i][x][y][z]);
			add(so[i][7][7][z],fo[i][x][y][z]),add(so[i][7][y][7],fo[i][x][y][z]),add(so[i][x][7][7],fo[i][x][y][z]),add(so[i][7][7][7],fo[i][x][y][z]);
		}
	}
	Mod.init(mod);
	int _=1;
	cin>>_;
	while(_--) solve();
	return 0;
}