#include <bits/stdc++.h>
// #define int int64_t
#define ALL(x) begin(x), end(x)
#define All(x, l, r) &x[l], &x[(r) + 1]
using namespace std;
void file() {
  freopen("1.in", "r", stdin);
  freopen("1.out", "w", stdout);
}
using ui = unsigned int;
using ll = long long;
using ull = unsigned long long;
using db = long double;
using Li = __int128_t;
template <typename T> using vec = vector<T>;

const int mod = 1e9 + 7;
void Add(int &x, int y) { if((x += y) >= mod) x -= mod; }
void Sub(int &x, int y) { if((x -= y) < 0) x += mod; }
int Sum(int x, int y) { return Add(x, y), x; } 
int Dif(int x, int y) { return Sub(x, y), x; }
int qpow(int x, int y) {
  int b = x, r = 1;
  for(; y; b = (ll)b * b % mod, y /= 2) if(y & 1) r = (ll)r * b % mod;
  return r;
}
int Inv(int x) { return qpow(x, mod - 2); }

const int nLim = 1e4 + 5;
array<array<int, nLim>, 7> pw;
array<array<array<array<int, 7>, 7>, 7>, nLim> odd, even;

void Init(int N) {
  for(int i = 1; i < 7; i++) {
    pw[i][0] = 1;
    for(int j = 1; j <= N; j++) {
      pw[i][j] = i * pw[i][j - 1] % 7;
    }
  }
  odd[0][0][0][0] = even[0][0][0][0] = 1;
  odd[1][0][0][0] = odd[1][1][2][3] = 1;
  for(int i = 2; i <= N / 2; i++) {
    odd[i] = odd[i - 1];
    int id = 2 * i - 1;
    for(int j = 0; j < 7; j++) {
      for(int k = 0; k < 7; k++) {
        for(int p = 0; p < 7; p++) {
          int nj = (j + pw[1][id]) % 7;
          int nk = (k + pw[2][id]) % 7;
          int np = (p + pw[3][id]) % 7;
          Add(odd[i][nj][nk][np], odd[i - 1][j][k][p]);
        }
      }
    }
  }
  even[1][1][1][1] = 1;
  for(int i = 2; i <= N / 2; i++) {
    even[i] = even[i - 1];
    int id = 2 * (i - 1);
    for(int j = 0; j < 7; j++) {
      for(int k = 0; k < 7; k++) {
        for(int p = 0; p < 7; p++) {
          int nj = (j + pw[1][id]) % 7;
          int nk = (k + pw[2][id]) % 7;
          int np = (p + pw[3][id]) % 7;
          Add(even[i][nj][nk][np], even[i - 1][j][k][p]);
        }
      }
    }
  }
}

void solve(int TT) {
  string str;
  cin >> str;
  int n = str.size(), res = 0, w = 1;
  for(int i = n - 1; ~i; i--) {
    if(!w) break;
    if(str[i] == '0') { w = 0; str[i]++; break; }
    str[i] = '0';
  }
  if(w) { str = " 1" + str; n++; }
  else str = " " + str;
  
  vec<int> so(4, 0), se(4, 0);
  for(int i = 1; i < n; i++) {
    int vl = str[i] - '0', p = n - i - 1;
    int le = p / 2 + 1, lo = (p + 1) / 2;
    if(!vl) continue;
    
    vec<vec<pair<int, int>>> vect(4);
    for(int j = 1; j < 4; j++) {
      for(int k = 0; k < 7; k++) {
        vect[j].emplace_back((k + 7 - so[j]) % 7, (k + 7 - se[j]) % 7);
      }
      for(int k = 1; k < 7; k++) { 
        vect[j].emplace_back((k + 7 - so[j]) % 7, (7 - k + 7 - se[j]) % 7);
      }
    }
    
    function <int()> solve0 = [&]() -> int {
      ll sum1 = 0, sum2 = 0;
      for(int j = 0; j < 7; j++) {
        for(int k = 0; k < 7; k++) {
          for(int p = 0; p < 7; p++) {
            sum1 += odd[lo][j][k][p];
            sum2 += even[le][j][k][p];
          }
        }
      }
      sum1 %= mod; sum2 %= mod;
      return sum1 * sum2 % mod;
    };
    
    function <int()> solve1 = [&]() -> int {
      Li res = 0;
      for(auto pr : vect[1]) {
        int x = pr.first, y = pr.second;
        ll sum1 = 0, sum2 = 0;
        for(int j = 0; j < 7; j++) {
          for(int k = 0; k < 7; k++) {
            sum1 += odd[lo][x][j][k];
            sum2 += even[le][y][j][k];
          }
        }
        sum1 %= mod; sum2 %= mod;
        res += sum1 * sum2;
      }
      return res % mod;
    };
    
    function <int()> solve2 = [&]() -> int {
      Li res = 0;
      for(auto pr : vect[2]) {
        int x = pr.first, y = pr.second;
        ll sum1 = 0, sum2 = 0;
        for(int j = 0; j < 7; j++) {
          for(int k = 0; k < 7; k++) {
            sum1 += odd[lo][j][x][k];
            sum2 += even[le][j][y][k];
          }
        }
        sum1 %= mod; sum2 %= mod;
        res += sum1 * sum2;
      }
      return res % mod;
    };
    
    function <int()> solve3 = [&]() -> int {
      Li res = 0;
      for(auto pr1 : vect[1]) {
        for(auto pr2 : vect[2]) {
          int x1 = pr1.first, y1 = pr1.second;
          int x2 = pr2.first, y2 = pr2.second;
          ll sum1 = 0, sum2 = 0;
          for(int j = 0; j < 7; j++) {
            sum1 += odd[lo][x1][x2][j];
            sum2 += even[le][y1][y2][j];
          }
          sum1 %= mod; sum2 %= mod;
          res += sum1 * sum2;
        }
      }
      return res % mod;
    };
    
    function <int()> solve4 = [&]() -> int {
      Li res = 0;
      for(auto pr : vect[3]) {
        int x = pr.first, y = pr.second;
        ll sum1 = 0, sum2 = 0;
        for(int j = 0; j < 7; j++) {
          for(int k = 0; k < 7; k++) {
            sum1 += odd[lo][j][k][x];
            sum2 += even[le][j][k][y];
          }
        }
        sum1 %= mod; sum2 %= mod;
        res += sum1 * sum2;
      }
      return res % mod;
    };
    
    function <int()> solve5 = [&]() -> int {
      Li res = 0;
      for(auto pr1 : vect[1]) {
        for(auto pr2 : vect[3]) {
          int x1 = pr1.first, y1 = pr1.second;
          int x2 = pr2.first, y2 = pr2.second;
          ll sum1 = 0, sum2 = 0;
          for(int j = 0; j < 7; j++) {
            sum1 += odd[lo][x1][j][x2];
            sum2 += even[le][y1][j][y2];
          }
          sum1 %= mod; sum2 %= mod;
          res += sum1 * sum2;
        }
      }
      return res % mod;
    };
    
    function <int()> solve6 = [&]() -> int {
      Li res = 0;
      for(auto pr1 : vect[2]) {
        for(auto pr2 : vect[3]) {
          int x1 = pr1.first, y1 = pr1.second;
          int x2 = pr2.first, y2 = pr2.second;
          ll sum1 = 0, sum2 = 0;
          for(int j = 0; j < 7; j++) {
            sum1 += odd[lo][j][x1][x2];
            sum2 += even[le][j][y1][y2];
          }
          sum1 %= mod; sum2 %= mod;
          res += sum1 * sum2;
        }
      }
      return res % mod;
    };
    
    function <int()> solve7 = [&]() -> int {
      Li res = 0;
      for(auto pr1 : vect[1]) {
        for(auto pr2 : vect[2]) {
          for(auto pr3 : vect[3]) {
            int x1 = pr1.first, y1 = pr1.second;
            int x2 = pr2.first, y2 = pr2.second;
            int x3 = pr3.first, y3 = pr3.second;
            res += (ll)odd[lo][x1][x2][x3] * even[le][y1][y2][y3];
          }
        }
      }
      return res % mod;
    };
    
    Add(res, solve0());
    Sub(res, solve1());
    Sub(res, solve2());
    Add(res, solve3());
    Sub(res, solve4());
    Add(res, solve5());
    Add(res, solve6());
    Sub(res, solve7());
    
    for(int j = 1; j < 4; j++) {
      if((n - i) & 1) (so[j] += pw[j][n - i]) %= 7;
      else (se[j] += pw[j][n - i]) %= 7;
    }
  }
  cout << res << "\n";
}

int32_t main() {
//  file();
  ios::sync_with_stdio(0); cin.tie(0);
  Init(1e4 + 3);
  int T = 1;
  cin >> T;
  for(int i = 1; i <= T; i++) solve(i);
  return 0;
}