human
Can you provide a Python code to print the result modulo 1 000 000 007 (10^9 + 7) given the following:
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].
try:
assistant
#Here is Python code to print the result modulo 1 000 000 007 (10^9 + 7).
    import sys
    from functools import lru_cache, cmp_to_key
    from heapq import merge, heapify, heappop, heappush
    # from math import *
    from collections import defaultdict as dd, deque, Counter as C
    from itertools import combinations as comb, permutations as perm
    from bisect import bisect_left as bl, bisect_right as br, bisect, insort
    from time import perf_counter
    from fractions import Fraction
    import copy
    from copy import deepcopy
    import time
    starttime = time.time()
    mod = int(pow(10, 9) + 7)
    mod2 = 998244353

    def data(): return sys.stdin.readline().strip()
    def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
    def L(): return list(sp())
    def sl(): return list(ssp())
    def sp(): return map(int, data().split())
    def ssp(): return map(str, data().split())
    def l1d(n, val=0): return [val for i in range(n)]
    def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

    # sys.setrecursionlimit(int(pow(10,6)))
    # from sys import stdin
    # input = stdin.buffer.readline
    # I = lambda : list(map(int,input().split()))
    # import sys
    # input=sys.stdin.readline

    sys.stdin = open("input.txt", "r")
    sys.stdout = open("output.txt", "w")
except:
    pass

MOD = 10 ** 9 + 7

for _ in range(L()[0]):
    n, k = L()

    ans = 1
    if n%2:
        ans = pow(1+pow(2,n-1,MOD),k,MOD)
        print(ans)
    else:
        for i in range(1,k+1):
            ans = pow(pow(2,i-1,MOD),n,MOD) + (pow(2,n-1,MOD)-1)*ans
            ans %= MOD

        print(ans)