#include<bits/stdc++.h>
#define ll long long
#define db double

using namespace std;

const int Mod = 1e9 + 7;

int f[5005][7][7][7][2];
int sum[5005][8][7][7][7];
int Fpow[10005][4];

void add(int &x, int y) {
    x += y, x >= Mod ? x -= Mod : 0;
}

void init() {
    Fpow[0][1] = Fpow[0][2] = Fpow[0][3] = 1; 
    for (int i = 1; i <= 10000; i++) {
        Fpow[i][1] = Fpow[i - 1][1];
        Fpow[i][2] = Fpow[i - 1][2] * 2 % 7;
        Fpow[i][3] = Fpow[i - 1][3] * 3 % 7;
    }
    f[0][0][0][0][0] = f[0][0][0][0][1] = 1;
    for (int p = 0; p <= 5000; p++) {
        if (p) {
            for (int t = 0; t < 7; t++) {
                for (int tt = 0; tt < 7; tt++) {
                    for (int ttt = 0; ttt < 7; ttt++) {
                        int a = (t + Fpow[(p - 1) << 1][1]) % 7;
                        int b = (tt + Fpow[(p - 1) << 1][2]) % 7;
                        int c = (ttt + Fpow[(p - 1) << 1][3]) % 7;
                        if (p != 1) add(f[p][t][tt][ttt][0], f[p - 1][t][tt][ttt][0]);
                        add(f[p][a][b][c][0], f[p - 1][t][tt][ttt][0]);

                        a = (t + Fpow[(p << 1) - 1][1]) % 7;
                        b = (tt + Fpow[(p << 1) - 1][2]) % 7;
                        c = (ttt + Fpow[(p << 1) - 1][3]) % 7;
                        add(f[p][t][tt][ttt][1], f[p - 1][t][tt][ttt][1]);
                        add(f[p][a][b][c][1], f[p - 1][t][tt][ttt][1]);
                    }
                }
            }
        }

        for (int sta = 0; sta < 8; sta++) {
            for (int t = 0; t < 7; t++) {
                for (int tt = 0; tt < 7; tt++) {
                    for (int ttt = 0; ttt < 7; ttt++) {
                        sum[p][sta][t][tt][ttt] = f[p][t][tt][ttt][1];
                    }
                }
            }
            if (sta & 4) {
                for (int t = 1; t < 7; t++) {
                    for (int tt = 0; tt < 7; tt++) {
                        for (int ttt = 0; ttt < 7; ttt++) {
                            add(sum[p][sta][t][tt][ttt], sum[p][sta][t - 1][tt][ttt]);
                        }
                    }
                }
            }
            if (sta & 2) {
                for (int t = 0; t < 7; t++) {
                    for (int tt = 1; tt < 7; tt++) {
                        for (int ttt = 0; ttt < 7; ttt++) {
                                add(sum[p][sta][t][tt][ttt], sum[p][sta][t][tt - 1][ttt]);
                        }
                    }
                }
            }
            
            if (sta & 1) {
                for (int t = 0; t < 7; t++) {
                    for (int tt = 0; tt < 7; tt++) {
                        for (int ttt = 1; ttt < 7; ttt++) {
                                add(sum[p][sta][t][tt][ttt], sum[p][sta][t][tt][ttt - 1]);
                        }
                    }
                }
            }
        }
    }
}

int calc(int len, vector<vector<int>> val) {
    int ans = 0;
    for (int t = 0; t < 7; t++) {
        for (int tt = 0; tt < 7; tt++) {
            for (int ttt = 0; ttt < 7; ttt++) {
                if (f[(len + 1) >> 1][t][tt][ttt][0]) {
                    int now[3] = {t, tt, ttt};
                    vector<int> lim[3];
                    for (int p = 0; p < 3; p++) {
                        int g = (now[p] + val[p][0] + 7 - val[p][1]) % 7;
                        int h = (7- (now[p] + val[p][0] + val[p][1]) % 7) % 7;
                        lim[p].push_back(-1);
                        lim[p].push_back(g);
                        if (g != h) {
                            lim[p].push_back(h);
                        }
                    }
                    ll res = 0;
                    for (auto a : lim[0]) {
                        for (auto b : lim[1]) {
                            for (auto c : lim[2]) {   
                                int sta = ((a == -1) << 2) | ((b == -1) << 1) | (c == -1);
                                int p = (a != -1) ^ (b != -1) ^ (c != -1);
                                if (p) res -= sum[len >> 1][sta][(a + 7) % 7][(b + 7) % 7][(c + 7) % 7];
                                else res += sum[len >> 1][sta][(a + 7) % 7][(b + 7) % 7][(c + 7) % 7];
                            }
                        }
                    }
                    res = (res % Mod + Mod) % Mod;
                    if (res) {
                        ans = (ans + 1ll * res * f[(len + 1) >> 1][t][tt][ttt][0]) % Mod;
                    }
                }
            }
        }
    }
    return ans;
}

bool check(vector<vector<int>> val) {
    for (int i = 0; i < 3; i++) {
        if (val[i][0] == val[i][1]) {
            return 0;
        }
        if ((val[i][0] + val[i][1]) % 7 == 0) {
            return 0;
        }
    }
    return 1;
}

void solve() {
    string s;
    cin >> s;
    int len =  s.size();
    vector<vector<int>> val(3, vector<int>(2));
    int ans = 0;
    for (int i = 0; i < len; i++) {
        if (s[i] == '1') {
                if (i != len - 1) {
                    add(ans, calc(len - i - 1, val));
                }
                for (int t = 0; t < 3; t++) {
                    val[t][(len - i - 1) & 1] = (val[t][(len - i - 1) & 1] + Fpow[len - i - 1][t + 1]) % 7;
                }
                if (i == len - 1) {
                    if (check(val)) {
                        ans++;
                    }
                }
        }
    }
    cout << ans << '\n';
}

int main() {
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}
/*
5
1
1010
110101
1000111000
101101001000
*/