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

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


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


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
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

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
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()))
	p = n * (n + 1) // 2 - ceil(n / 2) ** 2
	print(pow(m, p, MOD))


p = int(1000000000.0 + 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
	tot = num * (2 * num + 2) // 2
	print(pow(m, tot, mod))


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)