#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) {
        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;
}
void test() {
    string s; cin >> s;
    n = (int)s.size();
    for(int i = 1; i <= n; i++) {
        r[i] = (s[i - 1] - '0');
    }
    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]);
                if(b && ok({j, k}, 2, 3)) {
                    d = 1;
                }
                add(tdp[i][j][k][a][b][c][d], 1);
                tr.push_back({i, j, k, a, b, c, d});
            }
        }
    }
    
    sort(tr.begin(), tr.end());
    tr.resize(unique(tr.begin(), tr.end()) - tr.begin());
    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 && !_b && !_c && !_d) continue;
                add(dp[y][z][f][_a][_b][_c][_d], tdp[x][y][z][a][b][c][d]);
                nv.push_back({y, z, f, _a, _b, _c, _d});
            }
        }
        tr.swap(nv);
        sort(tr.begin(), tr.end());
        tr.resize(unique(tr.begin(), tr.end()) - tr.begin());
        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;
        }
    }
    sort(tr.begin(), tr.end());
    tr.resize(unique(tr.begin(), tr.end()) - tr.begin());
    
    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();
}