You have found $M$ different types of jewels in a mine and each type of jewel is present in an infinite number.
There are $N$ different boxes located at position $(1 ,2 ,3 ,...N)$.
Each box can collect jewels up to a certain number ( box at position $i$ have $i$ different partitions and each partition can collect at most one jewel of any type).
Boxes at odd positions are already fully filled with jewels while boxes at even positions are completely empty.
Print the total number of different arrangements possible so that all boxes can be fully filled.
As the answer can be very large you can print it by doing modulo with 1000000007(10^9+7).

-----Input:-----
- First line will contain $T$, number of testcases. 
- Each testcase contains of a single line of input, two integers $N ,  M$. 

-----Output:-----
For each testcase, Print the total number of different arrangement.

-----Constraints-----
- $1 \leq T \leq 20000$
- $1 \leq N \leq 1e9$
- $1 \leq M \leq 1e14$

-----Sample Input:-----
2
1 10
5 2

-----Sample Output:-----
1
64

Difficulty: interview

Starter code:

Solutions:
t = int(input())
while t != 0:
    M = 1000000007
    n, m = list(map(int, input().split())) 
    ans = 1
    tt = n//2
    tt = tt * (tt + 1)
    
    ans = pow(m, tt, M)
    
    print(ans)
    t -= 1
    
    


# cook your dish here
t = int(input())
for _ in range(t):
    nm = list(map(int,input().split()))
    if nm[0]==1 or nm[1]==1:
        print(1)
    else:
        k = nm[0]//2
        print(pow(nm[1],k*(k+1),10**9 + 7))

for _ in range(int(input())):
    n,m=list(map(int,input().split()))
    n=n//2
    n=n*(n+1)
    n=int(n)
    print(pow(m,n,1000000007))


from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353
def inp(): return stdin.readline().strip()
def out(var, end="\n"): stdout.write(str(var)+"\n")
def outa(*var, end="\n"): stdout.write(' '.join(map(str, var)) + end)
def lmp(): return list(mp())
def mp(): return list(map(int, inp().split()))
def smp(): return list(map(str, inp().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)]
def remadd(x, y): return 1 if x%y else 0
def ceil(a,b): return (a+b-1)//b

def isprime(x):
    if x<=1: return False
    if x in (2, 3): return True
    if x%2 == 0: return False
    for i in range(3, int(sqrt(x))+1, 2):
        if x%i == 0: return False
    return True
    
for _ in range(int(inp())):
    n, m = mp()
    x = n//2
    print(pow(m, x*(x+1), mod))


'''
      ___           ___                         ___                       ___           ___                         ___
     /\__\         /\  \         _____         /\  \                     /\  \         /\  \                       /\__\
    /:/ _/_        \:\  \       /::\  \        \:\  \       ___         /::\  \       |::\  \         ___         /:/ _/_
   /:/ /\  \        \:\  \     /:/\:\  \        \:\  \     /\__\       /:/\:\__\      |:|:\  \       /\__\       /:/ /\  \
  /:/ /::\  \   ___  \:\  \   /:/  \:\__\   ___ /::\  \   /:/__/      /:/ /:/  /    __|:|\:\  \     /:/  /      /:/ /::\  \
 /:/_/:/\:\__\ /\  \  \:\__\ /:/__/ \:|__| /\  /:/\:\__\ /::\  \     /:/_/:/__/___ /::::|_\:\__\   /:/__/      /:/_/:/\:\__\
 \:\/:/ /:/  / \:\  \ /:/  / \:\  \ /:/  / \:\/:/  \/__/ \/\:\  \__  \:\/:::::/  / \:\~~\  \/__/  /::\  \      \:\/:/ /:/  /
  \::/ /:/  /   \:\  /:/  /   \:\  /:/  /   \::/__/       ~~\:\/\__\  \::/~~/~~~~   \:\  \       /:/\:\  \      \::/ /:/  /
   \/_/:/  /     \:\/:/  /     \:\/:/  /     \:\  \          \::/  /   \:\~~\        \:\  \      \/__\:\  \      \/_/:/  /
     /:/  /       \::/  /       \::/  /       \:\__\         /:/  /     \:\__\        \:\__\          \:\__\       /:/  /
     \/__/         \/__/         \/__/         \/__/         \/__/       \/__/         \/__/           \/__/       \/__/

'''
"""
░░██▄░░░░░░░░░░░▄██
░▄▀░█▄░░░░░░░░▄█░░█░
░█░▄░█▄░░░░░░▄█░▄░█░
░█░██████████████▄█░
░█████▀▀████▀▀█████░
▄█▀█▀░░░████░░░▀▀███
██░░▀████▀▀████▀░░██
██░░░░█▀░░░░▀█░░░░██
███▄░░░░░░░░░░░░▄███
░▀███▄░░████░░▄███▀░
░░░▀██▄░▀██▀░▄██▀░░░
░░░░░░▀██████▀░░░░░░
░░░░░░░░░░░░░░░░░░░░
"""
import sys
import math
import collections
import operator as op
from collections import deque
from math import gcd, inf, sqrt, pi, cos, sin, ceil, log2, floor, log
from bisect import bisect_right, bisect_left, bisect

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

from functools import reduce
from sys import stdin, stdout, setrecursionlimit
setrecursionlimit(2**20)


def ncr(n, r):
    r = min(r, n - r)
    numer = reduce(op.mul, list(range(n, n - r, -1)), 1)
    denom = reduce(op.mul, list(range(1, r + 1)), 1)
    return numer // denom  # or / in Python 2


def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return (list(factors))


def isPowerOfTwo(x):
    return (x and (not(x & (x - 1))))

MOD = 1000000007  # 10^9 + 7
PMOD = 998244353
N = 10**18 + 1
LOGN = 30
alp = 'abcdefghijklmnopqrstuvwxyz'
T = 1
T = int(stdin.readline())
for _ in range(T):
    n, m = list(map(int, stdin.readline().rstrip().split()))
    # n = int(stdin.readline())
    # a = list(map(int, stdin.readline().rstrip().split()))
    # b = list(map(int, stdin.readline().rstrip().split()))
    # s = str(stdin.readline().strip('\n'))
    # s = list(stdin.readline().strip('\n'))
    # m = int(stdin.readline())
    # c = list(map(int, stdin.readline().rstrip().split()))
    p = (n * (n + 1)) // 2 - (ceil(n / 2))**2
    print(pow(m, p, MOD))


# cook your dish here
p = (int)(1e9+7) 
for _ in range(int(input())):
    n,m =map(int,input().split())
    if n%2!=0:
        n=(n-1)//2
    else:
        n=n//2
    b=n*(n+1)
    ans=pow(m,b,p)
    print(ans)

for _ in range(int(input())):
    mod=(10**9)+7
    n,m=map(int,input().split())
    n=n-(n%2)
    num=n//2
    ##print(num)
    tot=(num*((2*num)+2))//2

    print(pow(m,tot,mod))

# cook your dish here
mod=10**9+7
for _ in range (int(input())):
    n,m=map(int,input().split())
    num=n//2
    tot=(num*(2+2*num))//2
    print(pow(m,tot,mod))

# cook your dish here
def pw(x,n):
    if x==0:
        return 1
    r=1
    while n>0:
        if n%2:
            r=(r*x)%1000000007
        x=(x*x)%1000000007
        n//=2
    return r%1000000007
t=int(input())
while t>0:
    n,m=list(map(int,input().split()))
    n//=2
    n*=n+1
    print(pw(m,n))
    t-=1



MOD = 10 ** 9 + 7
for _ in range(int(input())):
    n, m = list(map(int, input().split()))
    x = n // 2

    print(pow(m, (x * (x + 1)), MOD))


t=int(input())
mod=10**9+7
for _ in range(t):
    a,b=list(map(int,input().split()))
    x=a//2
    d = (x*(x+1))
    ans  =pow(b,d,mod)
    print(ans)