#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e4+7;
const int MOD = 1e9 +7;
string ss;
int dp[100001][5][9];
int solve(int i,int j,int mod)
{
if(dp[i][j][mod]!=-1) return dp[i][j][mod];
if(i==ss.length() || j==5) return 0;
int mn = 0,pp = 0;
pp = (mod*10 + ss[i] - '0')%9;
//nah nah you would be counting the same steps again...
if(pp==0) mn++;
mn += (solve(i+1,j+1,pp) + solve(i+1,0,0)%MOD)%MOD; //case 1 if u are not ignoring...
dp[i][j][mod] = (mn + solve(i+1,j,mod)%MOD)%MOD; // case 2 if u are ignoring...
return mn;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
cin>>t;
while(t-->0)
{
cin>>ss;
memset(dp,-1,sizeof(dp));
int p = 0;
for(int i = 0;i<ss.length();i++) if((ss[i]-'0')==0) p++;
cout<<solve(0,0,0)-(1<<p - 1)<<'\n';
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKY29uc3QgaW50IE1BWCA9IDFlNCs3Owpjb25zdCBpbnQgTU9EID0gMWU5ICs3OwpzdHJpbmcgc3M7CmludCBkcFsxMDAwMDFdWzVdWzldOwoKaW50IHNvbHZlKGludCBpLGludCBqLGludCBtb2QpCnsKICBpZihkcFtpXVtqXVttb2RdIT0tMSkgcmV0dXJuIGRwW2ldW2pdW21vZF07CiAgaWYoaT09c3MubGVuZ3RoKCkgfHwgaj09NSkgcmV0dXJuIDA7CiAgaW50IG1uID0gMCxwcCA9IDA7CiAgcHAgPSAobW9kKjEwICsgc3NbaV0gLSAnMCcpJTk7CiAgLy9uYWggbmFoIHlvdSB3b3VsZCBiZSBjb3VudGluZyB0aGUgc2FtZSBzdGVwcyBhZ2Fpbi4uLgogIAogIGlmKHBwPT0wKSBtbisrOwogIG1uICs9IChzb2x2ZShpKzEsaisxLHBwKSArIHNvbHZlKGkrMSwwLDApJU1PRCklTU9EOyAvL2Nhc2UgMSBpZiB1IGFyZSBub3QgaWdub3JpbmcuLi4KICBkcFtpXVtqXVttb2RdID0gKG1uICsgc29sdmUoaSsxLGosbW9kKSVNT0QpJU1PRDsgLy8gY2FzZSAyIGlmIHUgYXJlIGlnbm9yaW5nLi4uCiAgcmV0dXJuIG1uOwp9CgppbnQgbWFpbigpCnsKICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICBjaW4udGllKDApOyBjb3V0LnRpZSgwKTsKICBpbnQgdDsKICBjaW4+PnQ7CiAgd2hpbGUodC0tPjApCiAgewogICAgY2luPj5zczsKICAgIG1lbXNldChkcCwtMSxzaXplb2YoZHApKTsKICAgIGludCAgcCA9IDA7CiAgICBmb3IoaW50IGkgPSAwO2k8c3MubGVuZ3RoKCk7aSsrKSBpZigoc3NbaV0tJzAnKT09MCkgcCsrOwoJICBjb3V0PDxzb2x2ZSgwLDAsMCktKDE8PHAgLSAxKTw8J1xuJzsKICB9CiAgcmV0dXJuIDA7Cn0K