1557_C. Moamen and XOR_186
Moamen and Ezzat are playing a game. They create an array a of n non-negative integers where every element is less than 2^k.

Moamen wins if a_1  \&  a_2  \&  a_3  \&  …  \&  a_n ≥ a_1 ⊕ a_2 ⊕ a_3 ⊕ … ⊕ a_n.

Here \& denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND), and ⊕ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

Please calculate the number of winning for Moamen arrays a.

As the result may be very large, print the value modulo 1 000 000 007 (10^9 + 7).

Input

The first line contains a single integer t (1 ≤ t ≤ 5)— the number of test cases. 

Each test case consists of one line containing two integers n and k (1 ≤ n≤ 2⋅ 10^5, 0 ≤ k ≤ 2⋅ 10^5).

Output

For each test case, print a single value — the number of different arrays that Moamen wins with.

Print the result modulo 1 000 000 007 (10^9 + 7).

Example

Input


3
3 1
2 1
4 0


Output


5
2
1

Note

In the first example, n = 3, k = 1. As a result, all the possible arrays are [0,0,0], [0,0,1], [0,1,0], [1,0,0], [1,1,0], [0,1,1], [1,0,1], and [1,1,1].

Moamen wins in only 5 of them: [0,0,0], [1,1,0], [0,1,1], [1,0,1], and [1,1,1].
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Solve6 {

    public static void main(String[] args) throws IOException {
        PrintWriter pw = new PrintWriter(System.out);
        new Solve6().solve(pw);
        pw.flush();
        pw.close();
    }

    public void solve(PrintWriter pw) throws IOException {
        FastReader sc = new FastReader();
        final int MOD = (int) 1E+9 + 7;
        final int MAX = (int) 2E+5;
        fact = new long[MAX + 1];
        fact[0] = 1;
        for (int i = 1; i <= MAX; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
        }
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt(), k = sc.nextInt();
            if (k == 0) {
                pw.println(1);
                continue;
            }
            long[] s = combinations(n, MOD);
            long ans = 0;
            for (int i = 0; i <= k; i++) {
                if ((n & 1) == 0) {
                    ans += pow(s[0], k - i, MOD) * (pow(s[2], Math.max(0, i - 1), MOD));
                } else {
                    ans += pow(s[0], k - i, MOD) * (pow(s[1], Math.max(0, i - 1), MOD));
                }
                ans %= MOD;
            }
            pw.println(ans);
        }
    }

    public long pow(long a, long n, int MOD) {
        if (n == 0) {
            return 1;
        }
        long y = pow(a, n >> 1, MOD);
        if ((n & 1) == 0) {
            return (y * y) % MOD;
        }
        return (a * ((y * y) % MOD)) % MOD;
    }
    long[] fact;

    public long[] combinations(int n, int MOD) {
        long[] s = new long[3];
        s[0] = 1;
        for (int i = 1; i < n; i++) {
            long ncr = ncr(n, i, MOD);
            if ((i & 1) == 1) {
                s[2] = (s[2] + ncr) % MOD;
            } else {
                s[0] = (s[0] + ncr) % MOD;
            }
        }
        s[2] = (s[2] + s[0] + 1) % MOD;
        s[1] = (s[0] + 1) % MOD;
        return s;
    }

    public long ncr(int n, int r, int MOD) {
        long denominator = (fact[n - r] * fact[r]) % MOD;
        long multiplicativeInverse = (extendedEuclidean(denominator, MOD)[1] + MOD) % MOD;
        long ans = (fact[n] * multiplicativeInverse) % MOD;
        return ans;
    }

    public long[] extendedEuclidean(long a, long b) {
        if (b == 0) {
            return new long[]{a, 1, 0};
        }
        long[] p = extendedEuclidean(b, a % b);
        long d = p[0], x1 = p[1], y1 = p[2];
        long x = y1, y = x1 - (a / b) * y1;
        return new long[]{d, x, y};
    }

    static class FastReader {

        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) {
            try {
                br = new BufferedReader(new FileReader(s));
            } catch (FileNotFoundException e) {
            }
        }

        public String next() {
            if (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            try {
                return br.readLine();
            } catch (Exception e) {
            }
            return null;
        }

        public boolean hasNext() throws IOException {
            if (st != null && st.hasMoreTokens()) {
                return true;
            }
            String s = br.readLine();
            if (s == null || s.isEmpty()) {
                return false;
            }
            st = new StringTokenizer(s);
            return true;
        }
    }
}
