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.
import java.io.*;
import java.util.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// ans = a008642[m]

public class cf1423j {

    static Map<Long, Integer> memo = new HashMap<>();

    public static void main(String[] args) throws IOException {
        int t = ri();
        long m[] = rla(t);

        /* int t = 50;
        long m[] = new long[t];
        for (int i = 0; i < t; ++i) {
            m[i] = i + 1;
        } */

        /* for (int i = 0; i < t; ++i) {
            prln(solve(m[i]));
        } */

        for (int i = 0; i < t; ++i) {
            prln(a(m[i]));
        }
        close();
    }

    static int mmod = 1000000007;
    static int inv32 = minv(32), inv8 = minv(8);

    // thank you oeis
    static int a(long m) {
        int n = (int) (m % mmod);
        // ans = (2 * n ^ 2 + 14 * n + 21 + (2 * n + 7) * (-1) ^ n) / 32 + ((1 + (-1) ^ n) / 2 - (1 - (-1) ^ n) * i / 2) * i ^ n / 8
        // a = 2 * n ^ 2
        // b = 14 * n
        // c = 2 * n + 7
        // d = (-1) ^ n
        // e = (1 + d) / 2
        // f = (1 - d) * i / 2
        // g = e - f
        // ans = (a + b + 21 + c * d) / 32 + g * i ^ n / 8
        int a = mmul(2, mpow(n, 2));
        int b = mmul(14, n);
        int c = madd(mmul(2, n), 7);
        int d = m % 2 == 0 ? 1 : -1;
        int e = (1 + d) / 2;
        int f = (1 - d) / 2;
        // g = (e, -f)
        // i ^ m = (m % 4 = 0) * (1, 0) + (m % 4 = 1) * (0, 1) + (m % 4 = 2) * (-1, 0) + (m % 4 = 3) * (0, -1)
        // re(g * i ^ m) = (m % 4 = 0) * e + (m % 4 = 1) * f + (m % 4 = 2) * (-e) + (m % 4 = 3) * (-f)
        int regim;
        if (m % 4 == 0) {
            regim = e;
        } else if (m % 4 == 1) {
            regim = f;
        } else if (m % 4 == 2) {
            regim = mmod - e;
        } else {
            regim = mmod - f;
        }
        return madd(mmul(madd(a, b, 21, mmul(c, (d + mmod) % mmod)), inv32), mmul(regim, inv8));
    }

    // lsb to hsb
    // tle on test 16
    static int solve(long m) {
        if (m < 0) {
            return 0;
        } else if (m <= 1) {
            return 1;
        }
        if (!memo.containsKey(m)) {
            memo.put(m, madd(solve(m / 2), solve(m / 2 - 1), solve(m / 2 - 2), solve(m / 2 - 3)));
            memo.put(m ^ 1, memo.get(m));
        }
        return memo.get(m);
    }

    static class c {
        int a, b;

        c(int _a, int _b) {
            a = (_a + mmod) % mmod;
            b = (_b + mmod) % mmod;
        }
    }

    static c c(int a, int b) {
        return new c(a, b);
    }

    static c c(int a) {
        return c(a, 0);
    }

    static c add(c a, c b) {
        return c(madd(a.a, b.a), madd(a.b, b.b));
    }

    static c sub(c a, c b) {
        return c(msub(a.a, b.a), msub(a.b, b.b));
    }

    static c mul(c a, c b) {
        return c(msub(mmul(a.a, b.a), mmul(a.b, b.b)), madd(mmul(a.a, b.b), mmul(a.b, b.a)));
    }

    static c mul(c a, int b) {
        return c(mmul(a.a, b), mmul(a.b, b));
    }

    static c pow(c a, long b) {
        if (a.a == 0 && a.b == 0) {
            return c(a.a, a.b);
        }
        c ans = c(1, 0);
        while (b > 0) {
            if ((b & 1) > 0) {
                ans = mul(ans, a);
            }
            a = mul(a, a);
            b >>= 1;
        }
        return ans;
    }

    static int madd(int a, int b) {
        return (a + b) % mmod;
    }

    static int madd(int... a) {
        int ans = a[0];
        for (int i = 1; i < a.length; ++i) {
            ans = madd(ans, a[i]);
        }
        return ans;
    }

    static int msub(int a, int b) {
        return (a - b + mmod) % mmod;
    }

    static int mmul(int a, int b) {
        return (int) ((long) a * b % mmod);
    }

    static int mmul(int... a) {
        int ans = a[0];
        for (int i = 1; i < a.length; ++i) {
            ans = mmul(ans, a[i]);
        }
        return ans;
    }

    static int minv(int x) {
        // return mpow(x, mmod - 2);
        return (exgcd(x, mmod)[0] % mmod + mmod) % mmod;
    }

    static int mpow(int a, long b) {
        if (a == 0) {
            return 0;
        }
        int ans = 1;
        while (b > 0) {
            if ((b & 1) > 0) {
                ans = mmul(ans, a);
            }
            a = mmul(a, a);
            b >>= 1;
        }
        return ans;
    }

    static BufferedReader __i = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter __o = new PrintWriter(new OutputStreamWriter(System.out));
    static StringTokenizer input;
    static Random __r = new Random();

    // references
    // IBIG = 1e9 + 7
    // IMAX ~= 2e9
    // LMAX ~= 9e18

    // constants
    static final int IBIG = 1000000007;
    static final int IMAX = 2147483647;
    static final int IMIN = -2147483648;
    static final long LMAX = 9223372036854775807L;
    static final long LMIN = -9223372036854775808L;

    // math util
    static int minof(int a, int b, int c) {
        return min(a, min(b, c));
    }

    static int minof(int... x) {
        if (x.length == 1) return x[0];
        if (x.length == 2) return min(x[0], x[1]);
        if (x.length == 3) return min(x[0], min(x[1], x[2]));
        int min = x[0];
        for (int i = 1; i < x.length; ++i) if (x[i] < min) min = x[i];
        return min;
    }

    static long minof(long a, long b, long c) {
        return min(a, min(b, c));
    }

    static long minof(long... x) {
        if (x.length == 1) return x[0];
        if (x.length == 2) return min(x[0], x[1]);
        if (x.length == 3) return min(x[0], min(x[1], x[2]));
        long min = x[0];
        for (int i = 1; i < x.length; ++i) if (x[i] < min) min = x[i];
        return min;
    }

    static int maxof(int a, int b, int c) {
        return max(a, max(b, c));
    }

    static int maxof(int... x) {
        if (x.length == 1) return x[0];
        if (x.length == 2) return max(x[0], x[1]);
        if (x.length == 3) return max(x[0], max(x[1], x[2]));
        int max = x[0];
        for (int i = 1; i < x.length; ++i) if (x[i] > max) max = x[i];
        return max;
    }

    static long maxof(long a, long b, long c) {
        return max(a, max(b, c));
    }

    static long maxof(long... x) {
        if (x.length == 1) return x[0];
        if (x.length == 2) return max(x[0], x[1]);
        if (x.length == 3) return max(x[0], max(x[1], x[2]));
        long max = x[0];
        for (int i = 1; i < x.length; ++i) if (x[i] > max) max = x[i];
        return max;
    }

    static int powi(int a, int b) {
        if (a == 0) return 0;
        int ans = 1;
        while (b > 0) {
            if ((b & 1) > 0) ans *= a;
            a *= a;
            b >>= 1;
        }
        return ans;
    }

    static long powl(long a, int b) {
        if (a == 0) return 0;
        long ans = 1;
        while (b > 0) {
            if ((b & 1) > 0) ans *= a;
            a *= a;
            b >>= 1;
        }
        return ans;
    }

    static int fli(double d) {
        return (int) d;
    }

    static int cei(double d) {
        return (int) ceil(d);
    }

    static long fll(double d) {
        return (long) d;
    }

    static long cel(double d) {
        return (long) ceil(d);
    }

    static int gcf(int a, int b) {
        return b == 0 ? a : gcf(b, a % b);
    }

    static long gcf(long a, long b) {
        return b == 0 ? a : gcf(b, a % b);
    }

    static int[] exgcd(int a, int b) {
        if (b == 0) return new int[]{1, 0};
        int[] y = exgcd(b, a % b);
        return new int[]{y[1], y[0] - y[1] * (a / b)};
    }

    static long[] exgcd(long a, long b) {
        if (b == 0) return new long[]{1, 0};
        long[] y = exgcd(b, a % b);
        return new long[]{y[1], y[0] - y[1] * (a / b)};
    }

    static int randInt(int min, int max) {
        return __r.nextInt(max - min + 1) + min;
    }

    static long mix(long x) {
        x += 0x9e3779b97f4a7c15L;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9L;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebL;
        return x ^ (x >> 31);
    }

    // array util
    static void reverse(int[] a) {
        for (int i = 0, n = a.length, half = n / 2; i < half; ++i) {
            int swap = a[i];
            a[i] = a[n - i - 1];
            a[n - i - 1] = swap;
        }
    }

    static void reverse(long[] a) {
        for (int i = 0, n = a.length, half = n / 2; i < half; ++i) {
            long swap = a[i];
            a[i] = a[n - i - 1];
            a[n - i - 1] = swap;
        }
    }

    static void reverse(double[] a) {
        for (int i = 0, n = a.length, half = n / 2; i < half; ++i) {
            double swap = a[i];
            a[i] = a[n - i - 1];
            a[n - i - 1] = swap;
        }
    }

    static void reverse(char[] a) {
        for (int i = 0, n = a.length, half = n / 2; i < half; ++i) {
            char swap = a[i];
            a[i] = a[n - i - 1];
            a[n - i - 1] = swap;
        }
    }

    static void shuffle(int[] a) {
        int n = a.length - 1;
        for (int i = 0; i < n; ++i) {
            int ind = randInt(i, n);
            int swap = a[i];
            a[i] = a[ind];
            a[ind] = swap;
        }
    }

    static void shuffle(long[] a) {
        int n = a.length - 1;
        for (int i = 0; i < n; ++i) {
            int ind = randInt(i, n);
            long swap = a[i];
            a[i] = a[ind];
            a[ind] = swap;
        }
    }

    static void shuffle(double[] a) {
        int n = a.length - 1;
        for (int i = 0; i < n; ++i) {
            int ind = randInt(i, n);
            double swap = a[i];
            a[i] = a[ind];
            a[ind] = swap;
        }
    }

    static void rsort(int[] a) {
        shuffle(a);
        sort(a);
    }

    static void rsort(long[] a) {
        shuffle(a);
        sort(a);
    }

    static void rsort(double[] a) {
        shuffle(a);
        sort(a);
    }

    static int[] copy(int[] a) {
        int[] ans = new int[a.length];
        for (int i = 0; i < a.length; ++i) ans[i] = a[i];
        return ans;
    }

    static long[] copy(long[] a) {
        long[] ans = new long[a.length];
        for (int i = 0; i < a.length; ++i) ans[i] = a[i];
        return ans;
    }

    static double[] copy(double[] a) {
        double[] ans = new double[a.length];
        for (int i = 0; i < a.length; ++i) ans[i] = a[i];
        return ans;
    }

    static char[] copy(char[] a) {
        char[] ans = new char[a.length];
        for (int i = 0; i < a.length; ++i) ans[i] = a[i];
        return ans;
    }

    // input
    static void r() throws IOException {
        input = new StringTokenizer(rline());
    }

    static int ri() throws IOException {
        return Integer.parseInt(rline());
    }

    static long rl() throws IOException {
        return Long.parseLong(rline());
    }

    static double rd() throws IOException {
        return Double.parseDouble(rline());
    }

    static int[] ria(int n) throws IOException {
        int[] a = new int[n];
        r();
        for (int i = 0; i < n; ++i) a[i] = ni();
        return a;
    }

    static int[] riam1(int n) throws IOException {
        int[] a = new int[n];
        r();
        for (int i = 0; i < n; ++i) a[i] = ni() - 1;
        return a;
    }

    static long[] rla(int n) throws IOException {
        long[] a = new long[n];
        r();
        for (int i = 0; i < n; ++i) a[i] = nl();
        return a;
    }

    static double[] rda(int n) throws IOException {
        double[] a = new double[n];
        r();
        for (int i = 0; i < n; ++i) a[i] = nd();
        return a;
    }

    static char[] rcha() throws IOException {
        return rline().toCharArray();
    }

    static String rline() throws IOException {
        return __i.readLine();
    }

    static String n() {
        return input.nextToken();
    }

    static int rni() throws IOException {
        r();
        return ni();
    }

    static int ni() {
        return Integer.parseInt(n());
    }

    static long rnl() throws IOException {
        r();
        return nl();
    }

    static long nl() {
        return Long.parseLong(n());
    }

    static double rnd() throws IOException {
        r();
        return nd();
    }

    static double nd() {
        return Double.parseDouble(n());
    }

    // output
    static void pr(int i) {
        __o.print(i);
    }

    static void prln(int i) {
        __o.println(i);
    }

    static void pr(long l) {
        __o.print(l);
    }

    static void prln(long l) {
        __o.println(l);
    }

    static void pr(double d) {
        __o.print(d);
    }

    static void prln(double d) {
        __o.println(d);
    }

    static void pr(char c) {
        __o.print(c);
    }

    static void prln(char c) {
        __o.println(c);
    }

    static void pr(char[] s) {
        __o.print(new String(s));
    }

    static void prln(char[] s) {
        __o.println(new String(s));
    }

    static void pr(String s) {
        __o.print(s);
    }

    static void prln(String s) {
        __o.println(s);
    }

    static void pr(Object o) {
        __o.print(o);
    }

    static void prln(Object o) {
        __o.println(o);
    }

    static void prln() {
        __o.println();
    }

    static void pryes() {
        prln("yes");
    }

    static void pry() {
        prln("Yes");
    }

    static void prY() {
        prln("YES");
    }

    static void prno() {
        prln("no");
    }

    static void prn() {
        prln("No");
    }

    static void prN() {
        prln("NO");
    }

    static boolean pryesno(boolean b) {
        prln(b ? "yes" : "no");
        return b;
    }

    ;

    static boolean pryn(boolean b) {
        prln(b ? "Yes" : "No");
        return b;
    }

    static boolean prYN(boolean b) {
        prln(b ? "YES" : "NO");
        return b;
    }

    static void prln(int... a) {
        for (int i = 0, len = a.length - 1; i < len; pr(a[i]), pr(' '), ++i) ;
        if (a.length > 0) prln(a[a.length - 1]);
        else prln();
    }

    static void prln(long... a) {
        for (int i = 0, len = a.length - 1; i < len; pr(a[i]), pr(' '), ++i) ;
        if (a.length > 0) prln(a[a.length - 1]);
        else prln();
    }

    static void prln(double... a) {
        for (int i = 0, len = a.length - 1; i < len; pr(a[i]), pr(' '), ++i) ;
        if (a.length > 0) prln(a[a.length - 1]);
        else prln();
    }

    static <T> void prln(Collection<T> c) {
        int n = c.size() - 1;
        Iterator<T> iter = c.iterator();
        for (int i = 0; i < n; pr(iter.next()), pr(' '), ++i) ;
        if (n >= 0) prln(iter.next());
        else prln();
    }

    static void h() {
        prln("hlfd");
        flush();
    }

    static void flush() {
        __o.flush();
    }

    static void close() {
        __o.close();
    }
}