#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
    
const int  N = 1e6 + 12, MOD = (int)1e9 + 7;

int n, r[N];
bool ok(vector<int> f, int l, int R) {
    vector<int> t;
    for(int i = l; i <= R; i++) {
        t.push_back(r[i]);
    }
    if(f == t) return true;
    sort(t.begin(), t.end());
    sort(f.begin(), f.end());
    if(t != f) return false;
    if((int)f.size() == 2) {
        return ((f[1] - f[0] == 1 && f[0] % 3 != 0) || f[1] - f[0] == 3);
    }
    if(f[1] - f[0] == 1 && f[3] - f[2] == 1 && f[2] - f[1] == 2 && (f[0] <= 2 || f[0] == 4 || f[0] == 5)) {
        return true;
    }
    return false;
}

void make() {
    if(n == 1) {
        cout << 1 << '\n';
        return;
    }
    if(n == 2) {
        cout << 1 + (abs(r[1] - r[2]) == 1 || abs(r[1] - r[2]) == 3) << '\n';
        return;
    }
}
int dp[10][10][10][2][2][2][2], tdp[10][10][10][2][2][2][2];
void add(int &x, int y) {
    x += y;
    if(x >= MOD) x -= MOD;
}
bool in(int x, int l, int R) {
    for(int i = l; i <= R; i++) {
        if(r[i] == x) return true;
    }
    return 0;
}
void test() {
    string s; cin >> s;
    n = (int)s.size();
    for(int i = 1; i <= n; i++) {
        r[i] = (s[i - 1] - '0');
    }
    for(int i = n + 1; i <= n + 5; i++) {
        r[i] = -1;
    }
    if(n <= 2) {
        make();
        return;
    }
    memset(dp, 0, sizeof(dp));
    memset(tdp, 0, sizeof(tdp));
    vector<array<int, 7>> tr;
    for(int i = 1; i <= 9; i++) {
        for(int j = 1; j <= 9; j++) {
            for(int k = 1; k <= 9; k++) {   
                bool a = 1, b = (r[1] == i), c = ok({i, j}, 1, 2), d = (c && k == r[3]);
                int y = i, z = j, f = k;
                if(b && ok({j, k}, 2, 3)) {
                    d = 1;
                }
                if(a) {
                    if(!in(y, 1, 4) || !in(z, 1, 4) || !in(f, 1, 4)) {
                        a = 0;
                    }
                }
                if(b) {
                    if(!in(z, 2, 5) || !in(f, 2, 5)) {
                        b = 0;
                    }
                }
                if(c) {
                    if(!in(f, 3, 6)) {
                        c = 0;
                    }
                }
                if(!tdp[i][j][k][a][b][c][d]) tr.push_back({i, j, k, a, b, c, d});
                add(tdp[i][j][k][a][b][c][d], 1);
            }
        }
    }
    
    int res = 0;
    for(int i = 3; i < n; i++) {
        vector<array<int, 7>> nv;
        for(auto [x, y, z, a, b, c, d]:tr) {
            for(int f = 1; f <= 9; f++) {
                int _a = b, _b = c, _c = d, _d = 0;
                if(d && f == r[i + 1]) _d = 1;
                if(c && ok({z, f}, i, i + 1)) _d = 1;
                if(a && ok({x, y, z, f}, i - 2, i + 1)) _d = 1;
                if(_a) {
                    if(!in(y, i - 1, i + 3) || !in(z, i - 1, i + 3) || !in(f, i - 1, i + 3)) {
                        _a = 0;
                    }
                }
                if(_b) {
                    if(!in(z, i, i + 4) || !in(f, i, i + 4)) {
                        _b = 0;
                    }
                }
                if(_c) {
                    if(!in(f, i + 1, i + 5)) {
                        _c = 0;
                    }
                }
                if(!_a && !_b && !_c && !_d) continue;
                int val = tdp[x][y][z][a][b][c][d];
                int Y = y, Z = z, F = f;
                if(!_a && !_b && !_c) F = 0;
                if(!_a && !_b ) Z = 0;
                if(!_a) Y =0 ;
                if(!dp[Y][Z][F][_a][_b][_c][_d]) nv.push_back({Y, Z, F, _a, _b, _c, _d});
                add(dp[Y][Z][F][_a][_b][_c][_d], val);
            }
        }
        tr.swap(nv);
        for(auto [x, y, z, a, b, c, d]:tr) {
            tdp[x][y][z][a][b][c][d] = dp[x][y][z][a][b][c][d];
            dp[x][y][z][a][b][c][d] = 0;
        }
    }
    for(auto [x, y, z, a, b, c, d]:tr) {
        if(d) {
            add(res, tdp[x][y][z][a][b][c][d]);
        }
    }
    cout << res << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t = 1; 
    cin >> t;

    while(t--) 
        test();
}