The Bubble Cup hypothesis stood unsolved for 130 years. Who ever proves the hypothesis will be regarded as one of the greatest mathematicians of our time! A famous mathematician Jerry Mao managed to reduce the hypothesis to this problem:

Given a number m, how many polynomials P with coefficients in set {\{0,1,2,3,4,5,6,7\}} have: P(2)=m?

Help Jerry Mao solve the long standing problem!

Input

The first line contains a single integer t (1 ≤ t ≤ 5⋅ 10^5) - number of test cases.

On next line there are t numbers, m_i (1 ≤ m_i ≤ 10^{18}) - meaning that in case i you should solve for number m_i.

Output

For each test case i, print the answer on separate lines: number of polynomials P as described in statement such that P(2)=m_i, modulo 10^9 + 7.

Example

Input


2
2 4


Output


2
4

Note

In first case, for m=2, polynomials that satisfy the constraint are x and 2.

In second case, for m=4, polynomials that satisfy the constraint are x^2, x + 2, 2x and 4.
#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 5, M = 1e3 + 5;
const long long INF = 1e18 + 5;
namespace INPUT_SPACE {
const int BS = (1 << 24) + 5;
char Buffer[BS], *HD, *TL;
char gc() {
  if (HD == TL) TL = (HD = Buffer) + fread(Buffer, 1, BS, stdin);
  return (HD == TL) ? EOF : *HD++;
}
inline unsigned long long read() {
  unsigned long long x, ch;
  while (((ch = gc()) < '0' || ch > '9'))
    ;
  x = ch ^ '0';
  while ((ch = gc()) >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ '0');
  return x;
}
}  // namespace INPUT_SPACE
using INPUT_SPACE::read;
char sws[30000011], tt[21];
int ssl, ttl;
inline int write(int x) {
  if (!x) sws[++ssl] = '0';
  for (ttl = 0; x; x /= 10) tt[++ttl] = char(x % 10 + '0');
  for (; ttl; ttl--) sws[++ssl] = tt[ttl];
  return sws[++ssl] = '\n';
}
inline int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
inline long long ab(long long x) { return x < 0 ? -x : x; }
inline long long fpow(long long qwe, long long asd, long long zxc) {
  if (asd < 0) return 0;
  long long a = qwe, b = 1, c = asd;
  while (c) {
    if (c & 1) b = b * a % zxc;
    a = a * a % zxc;
    c >>= 1;
  }
  return b;
}
int m1[8][8] = {1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0,
                0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0,
                0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0,
                0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0};
int m0[8][8] = {1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0,
                0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0,
                0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0,
                0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1};
int mat[65537][8][8], tmp[8][8];
unsigned long long p = 1e9 + 7;
inline void csh() {
  int sx = 2;
  for (int i = 0; i < 7; ++i) {
    for (int j = 0; j < 7; ++j) {
      mat[0][i][j] = m0[i][j];
      mat[1][i][j] = m1[i][j];
    }
  }
  for (int i = 1; i < 16; ++i) {
    for (int j = 0; j < sx; ++j) {
      int sz = j;
      for (int x = 0; x < 7; ++x) {
        for (int y = 0; y < 7; ++y) {
          tmp[x][y] = mat[j][x][y];
        }
      }
      for (int x = 0; x < 7; ++x) {
        for (int y = 0; y < 7; ++y) {
          mat[sz][x][y] = 0;
          for (int z = 0; z < 7; ++z) {
            mat[sz][x][y] = (mat[sz][x][y] + tmp[x][z] * m0[z][y]) % p;
          }
        }
      }
      sz |= (1 << i);
      for (int x = 0; x < 7; ++x) {
        for (int y = 0; y < 7; ++y) {
          mat[sz][x][y] = 0;
          for (int z = 0; z < 7; ++z) {
            mat[sz][x][y] = (mat[sz][x][y] + tmp[x][z] * m1[z][y]) % p;
          }
        }
      }
    }
    sx += (1 << i);
  }
}
int main() {
  csh();
  int t = read();
  while (t) {
    --t;
    unsigned long long n = read(), x = (1 << 16) - 1;
    unsigned long long dp[8] = {1, 0, 0, 0, 0, 0, 0, 0}, dpt[8];
    while (n) {
      unsigned long long y = n & x;
      for (int i = 0; i < 7; ++i) {
        dpt[i] = 0;
        for (int j = 0; j < 7; ++j) {
          dpt[i] = (dpt[i] + dp[j] * mat[y][j][i]);
        }
      }
      for (int i = 0; i < 7; ++i) dp[i] = dpt[i] % p;
      n >>= 16;
    }
    write(dp[0]);
  }
  fwrite(sws + 1, sizeof(char), ssl, stdout);
}
