#include <algorithm>
#include <array>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <vector>

using namespace std;

constexpr int N = 1e4, N6 = N / 6 + 2, T = 10, mod = 1e9 + 7, pw7[]{1, 7, 49, 343, 2401};

auto& mul(auto&& a, auto b) { return a = a * (uint64_t)b % mod; }
auto& add(auto&& a, auto b) { return a -= (a += b) >= mod? mod: 0; }
int sub7(int a, int b) { return a += (a -= b) < 0? 7: 0; }

int cnk[N6], c7[N6][7];

int calc_worst(const string& s, const vector<array<int, 6>>& bad) {
  int ans = 0;
  array<int, 6> pref{};
  pref[5] = 1;
  for (int i = 0; i < s.size(); ++i) if (s[i]) {
    int q = (s.size() - i - 1) / 6, r = (s.size() - i - 1) % 6;
    for (auto& b: bad) {
      int cur = 1;
      #pragma GCC unroll 9
      for (int i = 0; i < 6; ++i) mul(cur, c7[q + (i < r)][sub7(b[i], pref[i])]);
      add(ans, cur);
    }
    ++pref[(s.size() - i - 1) % 6] %= 7;
  }
  return ans;
}

int ans[T], cans[T], dp[2][pw7[4]];
string s[T];
array<int, 6> pref[T];

template <size_t n>
void calc_best(array<int, n> bad) {
  int mlen = 0;
  for (int i = 0; i < T; ++i) if (pref[i] = {}, cans[i] = 0, mlen = max(mlen, {s[i].size()}), 1)
  for (int j = 0; j < s[i].size(); ++j)
  for (int k = 0; k < n; ++k) pref[i][k] = (pref[i][k] * bad[k] + s[i][j]) % 7;
  for (int i = 0; i < T; ++i)
  for (int k = 0; k < n; ++k) {
    int t = 1;
    for (int j = 5; j--; ) t = t * bad[k] % 7;
    pref[i][k] = (pref[i][k] + t) % 7;
  }
  constexpr int sz = pw7[n];
  fill_n(dp[0], sz, 0);
  dp[0][0] = 1;
  int cpw[n];
  fill_n(cpw, n, 6);
  auto plain = [](auto... xs) { int x = 0; return ((x = x * 7 + xs), ...); };
  for (int i = 0; i < mlen; ++i) {
    for (int j = 0; j < T; ++j) if (s[j].size() >= i)
    for (int k = 0; k < n; ++k) pref[j][k] = (pref[j][k] + s[j].rbegin()[i] * cpw[k]) % 7;
    auto& cur = dp[i & 1], & nx = dp[~i & 1];
    for (int j = 0; j < T; ++j) if (s[j].size() > i && s[j].rbegin()[i]) {
      int idx = 0;
      for (int i = 0; i < n; ++i) idx = idx * 7 + pref[j][i];
      add(cans[j], cur[idx]);
    }
    if constexpr (n == 4) {
      for (int a0 = 0; a0 < 7; ++a0)
      for (int a1 = 0; a1 < 7; ++a1)
      for (int a2 = 0; a2 < 7; ++a2)
      #pragma GCC unroll 9
      for (int a3 = 0; a3 < 7; ++a3) {
        nx[plain(a0, a1, a2, a3)] = add(+cur[plain(a0, a1, a2, a3)], cur[plain(sub7(a0, cpw[0]), sub7(a1, cpw[1]), sub7(a2, cpw[2]), sub7(a3, cpw[3]))]);
      }
    } else if constexpr (n == 3) {
      for (int a0 = 0; a0 < 7; ++a0)
      for (int a1 = 0; a1 < 7; ++a1)
      #pragma GCC unroll 9
      for (int a2 = 0; a2 < 7; ++a2) {
        nx[plain(a0, a1, a2)] = add(+cur[plain(a0, a1, a2)], cur[plain(sub7(a0, cpw[0]), sub7(a1, cpw[1]), sub7(a2, cpw[2]))]);
      }
    } else if constexpr (n == 2) {
      for (int a0 = 0; a0 < 7; ++a0)
      for (int a1 = 0; a1 < 7; ++a1) {
        nx[plain(a0, a1)] = add(+cur[plain(a0, a1)], cur[plain(sub7(a0, cpw[0]), sub7(a1, cpw[1]))]);
      }
    } else if constexpr (n == 1) {
      for (int a0 = 0; a0 < 7; ++a0) {
        nx[plain(a0)] = add(+cur[plain(a0)], cur[plain(sub7(a0, cpw[0]))]);
      }
    }
    for (int i = 0; i < n; ++i) cpw[i] = cpw[i] * bad[i] % 7;
  }
  for (int i = 0; i < T; ++i) add(ans[i], n % 2? mod - cans[i]: cans[i]);
}


int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (int i = 0; i < N6; ++i)
  for (int j = 0; j <= i; ++j) add(c7[i][j % 7], !j? cnk[j] = 1: add(cnk[j], cnk[j - 1]));
  int t; cin >> t;
  for (int i = 0; i < t; ++i) {
    cin >> s[i];
    for (auto& c: s[i]) c -= '0';
    s[i].insert(s[i].begin(), 0);
    for (int j = s[i].size(); j--; ) if (s[i][j]++) s[i][j] = 0; else break;
    s[i].pop_back();
    for (auto c: s[i]) ans[i] = (ans[i] * 2 + c) % mod;
  }
  constexpr int cutoff = 4;
  {
    vector<array<int, 6>> bad[7];
    for (int i = 0; i < pow(7, 6); ++i) {
      array<int, 6> d;
      for (int j = 6, t = i; j--; t /= 7) d[j] = t % 7;
      int badness = 0;
      for (int j = 7; --j; ) {
        int s = 0;
        for (auto d: d) s = (s * j + d) % 7;
        badness += !s;
      }
      for (int j = cutoff; j++ < badness; ) bad[j].insert(bad[j].end(), badness == j? 1: j == badness - 1? badness: badness * (badness - 1) / 2, d);
    }
    for (int i = 0; i < T; ++i)
    for (int j = cutoff; j++ < 6; ) {
      auto t = calc_worst(s[i], bad[j]);
      add(ans[i], j % 2? mod - t: t);
    }
  }
  for (int m = 0; m < 1 << 6; ++m) if (__builtin_popcount(m) <= cutoff) {
    vector<int> v;
    for (int i = 0; i < 6; ++i) if (m & 1 << i) v.push_back(i + 1);
    if (v.size() == 4) calc_best<4>({v[0], v[1], v[2], v[3]});
    else if (v.size() == 3) calc_best<3>({v[0], v[1], v[2]});
    else if (v.size() == 2) calc_best<2>({v[0], v[1]});
    else if (v.size() == 1) calc_best<1>({v[0]});
  }
  for (int i = 0; i < t; ++i) cout << ans[i] << '\n';
}