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>
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
const int Inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3fll;
template <int jt>
struct ModInt {
  int x;
  ModInt(int v = 0) {
    x = v;
    if (x >= jt || x < 0) {
      x %= jt;
      if (x < 0) x += jt;
    }
  }
  ModInt(long long v) {
    x = v % jt;
    if (x < 0) x += jt;
  }
  operator int() const { return x; }
  friend inline ModInt &operator+=(ModInt &a, const ModInt &b) {
    a.x += b.x;
    if (a.x >= jt) a.x -= jt;
    return a;
  }
  friend inline ModInt operator+(ModInt a, const ModInt &b) { return a += b; }
  friend inline ModInt operator+(ModInt a, int b) { return a += ModInt(b); }
  friend inline ModInt operator+(int a, ModInt b) { return b += ModInt(a); }
  friend inline ModInt &operator++(ModInt &a) { return a += 1; }
  friend inline ModInt &operator-=(ModInt &a, const ModInt &b) {
    a.x -= b.x;
    if (a.x < 0) a.x += jt;
    return a;
  }
  friend inline ModInt operator-(ModInt a, const ModInt &b) { return a -= b; }
  friend inline ModInt operator-(ModInt a, int b) { return a -= ModInt(b); }
  friend inline ModInt operator-(int a, ModInt b) { return ModInt(a) - b; }
  friend inline ModInt &operator--(ModInt &a) { return a -= 1; }
  friend inline ModInt &operator*=(ModInt &a, const ModInt &b) {
    a.x = (long long)a.x * b.x % jt;
    return a;
  }
  friend inline ModInt operator*(ModInt a, const ModInt &b) { return a *= b; }
  friend inline ModInt operator*(ModInt a, int b) { return a *= ModInt(b); }
  friend inline ModInt operator*(int a, ModInt b) { return b *= ModInt(a); }
  static inline void exgcd(long long a, long long b, long long &x,
                           long long &y) {
    b ? (exgcd(b, a % b, y, x), y -= a / b * x) : (x = 1, y = 0);
  }
  friend inline ModInt inv(const ModInt &a) {
    long long x, y;
    exgcd(a, jt, x, y);
    return x;
  }
  friend inline ModInt operator/(const ModInt &a, const ModInt &b) {
    return a * inv(b);
  }
  friend inline ModInt operator/(ModInt a, int b) { return a * inv(ModInt(b)); }
  friend inline ModInt operator/(int a, ModInt b) { return ModInt(a) * inv(b); }
  friend inline ModInt operator/=(ModInt &a, const ModInt &b) {
    return a = a / b;
  }
};
const int jt = 1000000007;
ModInt<jt> dp[64][8], qzh[64][8];
int hv[64];
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    long long n;
    scanf("%lld", &n);
    for (int i = 0; i < (61); i++) hv[i] = ((n >> i) & 1);
    memset(dp, 0, sizeof(dp));
    memset(qzh, 0, sizeof(qzh));
    dp[61][0] = 1;
    qzh[61][0] = 1;
    for (register int i = 60; ~i; --i) {
      for (register int j = 0; j < 4; j++) {
        dp[i][j << 1] += qzh[i + 1][j << 1];
        dp[i][j << 1 | 1] += qzh[i + 1][j << 1 | 1];
      }
      for (register int j = 0; j < 4; j++) {
        register int nj = j << 1;
        qzh[i][nj] = dp[i][j] + dp[i][j + 1] + dp[i][j + 2] + dp[i][j + 3];
        if (hv[i])
          qzh[i][nj | 1] =
              dp[i][j] + dp[i][j + 1] + dp[i][j + 2] + dp[i][j + 3];
        else {
          qzh[i][nj | 1] = dp[i][j + 1] + dp[i][j + 2] + dp[i][j + 3];
          if (j + 4 < 16) qzh[i][nj | 1] += dp[i][j + 4];
        }
      }
    }
    ModInt<jt> sum = 0;
    for (int j = 0; j < (4); j++) sum += dp[0][j];
    printf("%d\n", int(sum));
  }
  return 0;
}
