You are given a square matrix $M$ with $N$ rows (numbered $1$ through $N$) and $N$ columns (numbered $1$ through $N$). Initially, all the elements of this matrix are equal to $A$. The matrix is broken down in $N$ steps (numbered $1$ through $N$); note that during this process, some elements of the matrix are simply marked as removed, but all elements are still indexed in the same way as in the original matrix. For each valid $i$, the $i$-th step consists of the following:
- Elements $M_{1, N-i+1}, M_{2, N-i+1}, \ldots, M_{i-1, N-i+1}$ are removed.
- Elements $M_{i, N-i+1}, M_{i, N-i+2}, \ldots, M_{i, N}$ are removed.
- Let's denote the product of all $2i-1$ elements removed in this step by $p_i$. Each of the remaining elements of the matrix (those which have not been removed yet) is multiplied by $p_i$.
Find the sum $p_1 + p_2 + p_3 + \ldots + p_N$. Since this number could be very large, compute it modulo $10^9+7$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains two space-separated integers $N$ and $A$.

-----Output-----
For each test case, print a single line containing one integer ― the sum of products at each step modulo $10^9+7$.

-----Constraints-----
- $1 \le T \le 250$
- $1 \le N \le 10^5$
- $0 \le A \le 10^9$
- the sum of $N$ over all test cases does not exceed $10^5$

-----Example Input-----
1
3 2

-----Example Output-----
511620149

-----Explanation-----
Example case 1:

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Mathematics

Number theory

Implementation


Solutions:
n = int(input())
for i in range(n):
	(k, l) = map(int, input().split())
	bc = l
	ans = 0
	kp = 1000000007
	for j in range(1, k + 1):
		l = pow(bc, 2 * j - 1, kp)
		ans = (l + ans) % kp
		bc = l * bc % kp
	print(ans)


m = 1000000007
n = int(input())
for _ in range(n):
	(a, p) = map(int, input().split())
	add = 0
	box = 1
	for i in range(a):
		q = pow(p, box, m)
		add += q
		add = add % m
		p = p % m
		p = p * q
		box += 2
	print(add % (m + 7))


def fastExpo(base, expo):
	res = 1
	while expo:
		if expo % 2 == 1:
			res = res * base % mod
		base = base * base % mod
		expo //= 2
	return res % mod
T = int(input())
for case in range(1, T + 1):
	(N, A) = map(int, input().split())
	mod = 10 ** 9 + 7
	tot = 0
	num = 1
	for i in range(N):
		p = fastExpo(A, num)
		num += 2
		A = A * p % mod
		tot = (tot + p) % mod
	print(tot)


t = int(input())
for i in range(t):
	(n, a) = map(int, input().split())
	sum1 = 0
	for j in range(n):
		p = pow(a, 2 * j + 1, 1000000007)
		sum1 += p
		sum1 %= 1000000007
		a *= p
		a %= 1000000007
	print(sum1 % 1000000007)


import sys, math, itertools, random, bisect
from collections import defaultdict
INF = 10 ** 18

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, a) = get_ints()
	num = 1
	tot = 0
	p = 1
	for i in range(n):
		pp = pow(a * p % mod, num, mod)
		num += 2
		p = p * pp % mod
		tot = (tot + pp) % mod
	print(tot)


z = int(1000000000.0 + 7)
for i in range(int(input())):
	(n, a) = map(int, input().split())
	x = 0
	for j in range(n):
		c = pow(a, 2 * j + 1, z)
		x += c
		x = x % z
		a = a * c
		a = a % z
	print(x)


for _ in range(int(input())):
	(n, a) = map(int, input().split())
	m = 10 ** 9 + 7
	p = 1
	f = 0
	l = a
	prev = 1
	for i in range(1, n + 1):
		a = l * prev
		p = pow(a, 2 * i - 1, m)
		prev = prev * p % m
		f = (f + p) % m
	print(f % m)


mod = 1000000007
for _ in range(int(input())):
	(n, a) = list(map(int, input().split()))
	(p, ans) = (1, 0)
	for i in range(n):
		a1 = pow(a, p, mod)
		ans = (ans + a1) % mod
		a = a * a1 % mod
		p += 2
	print(ans)


for _ in range(int(input())):
	(n, a) = list(map(int, input().split()))
	sum = 0
	mod = 10 ** 9 + 7
	a1 = a
	for i in range(1, n + 1):
		p = 2 * i - 1
		a = pow(a, p, mod)
		sum = (sum + a % mod) % mod
		a = a1 * a
		a = a % mod
		a1 = a
	print(sum)


mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(n, a) = map(int, input().split())
	ans = 0
	for i in range(1, 2 * n, 2):
		ans = (ans + pow(a, i, mod)) % mod
		a = a * pow(a, i, mod) % mod
	ans = ans % mod
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, a) = map(int, input().split())
	ans = 0
	prev = a
	fact = 1
	comeon = 1
	for i in range(n):
		comeon = comeon * prev % (10 ** 9 + 7)
		prev = pow(comeon, fact, 10 ** 9 + 7)
		ans = (ans + prev) % (10 ** 9 + 7)
		fact = fact + 2
	print(ans % (10 ** 9 + 7))


t = int(input())
for i in range(t):
	(n, v) = list(map(int, input().split()))
	j = 1
	product = 0
	while j <= n:
		c = pow(v, 2 * j - 1, 1000000007)
		product += c
		product %= 1000000007
		v = c * v
		v %= 1000000007
		j = j + 1
	print(product % 1000000007)


mod = 1000000007
t = int(input())
for _ in range(t):
	(n, a) = map(int, input().split())
	hak = 0
	for i in range(n):
		temp = pow(a, 2 * i + 1, mod)
		hak = (hak + temp) % mod
		a = a * temp % mod
	print(hak)


MOD = 10 ** 9 + 7
for _ in range(int(input())):
	(n, a) = list(map(int, input().split()))
	res = 0
	base = a
	for i in range(n):
		curr = pow(base, 2 * i + 1, MOD)
		res += curr
		res %= MOD
		base = base * curr
		base %= MOD
	print(res % MOD)


import sys

def getInt():
	return map(int, sys.stdin.readline().strip().split())

def getArray():
	return list(map(int, sys.stdin.readline().strip().split()))

def getStr():
	return sys.stdin.readline().strip()

def into():
	return int(sys.stdin.readline().strip())

def power(base, power):
	MOD = 1000000007
	result = 1
	while power > 0:
		if power % 2 == 1:
			result = result * base % MOD
		power = power // 2
		base = base * base % MOD
	return result
t = into()
while t:
	(N, A) = getInt()
	currentValueMatrix = A
	ans = 0
	MOD = 1000000007
	i = 1
	while i <= N:
		elementsToBeMultiplied = 2 * i - 1
		multipliedElements = power(currentValueMatrix, elementsToBeMultiplied) % MOD
		currentValueMatrix = currentValueMatrix * multipliedElements % MOD
		ans = (ans + multipliedElements) % MOD
		i += 1
	print(ans % MOD)
	t -= 1


for i in range(int(input())):
	(n, k) = map(int, input().split())
	mod = 1000000007
	s = 0
	for i in range(1, n + 1):
		p = pow(k, 2 * i - 1, mod)
		s = (s + p) % mod
		k = p * k % mod
	print(s)


for _ in range(int(input())):
	(N, A) = map(int, input().split())
	p = 1
	ans = 0
	for i in range(0, N):
		A %= 1000000007
		A *= p
		p = pow(A, 2 * i + 1, 1000000007)
		ans += p
	print(ans % 1000000007)


def raise_to_power(value, a, m, D):
	if a == 0:
		return 1
	elif a == 1:
		return value
	elif a in D:
		return D[a]
	else:
		D[a] = raise_to_power(value, a // 2, m, D) % m * (raise_to_power(value, a - a // 2, m, D) % m) % m
		return D[a]
m = 10 ** 9 + 7
T = int(input())
ans = []
for _ in range(T):
	(N, A) = [int(i) for i in input().split()]
	value = A
	sum = 0
	for i in range(N):
		x = raise_to_power(value, 2 * i + 1, m, {})
		sum = (sum % m + x) % m
		value = value % m * x % m
	ans.append(sum)
for i in ans:
	print(i)


def solve():
	(N, K) = map(int, input().split())
	mod = 10 ** 9 + 7
	m = 0
	for i in range(1, N + 1):
		c = pow(K, 2 * i - 1, mod)
		K *= c
		K %= mod
		m += c
		m %= mod
	print(m)

def __starting_point():
	t = int(input())
	while t != 0:
		solve()
		t -= 1
__starting_point()


def pingalapower(a, n, mod):
	if n == 1:
		return a
	x = pingalapower(a, n // 2, mod)
	if n % 2 == 0:
		return x * x % mod
	else:
		return x * x * a % mod
for _ in range(int(input())):
	(n, a) = map(int, input().split())
	c = 1
	ans = 0
	mod = 10 ** 9 + 7
	for i in range(n):
		t_1 = pingalapower(a, c, mod) % mod
		ans = (ans + t_1) % mod
		a = a * t_1 % mod
		c += 2
	print(ans % mod)


t = int(input())

def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
for i in range(t):
	(n, a) = map(int, input().split())
	total = 0
	for i in range(n):
		rem = 2 * i + 1
		mul = int(pow_mod(a, rem, 1000000007))
		a = a * mul % 1000000007
		total += mul
		total = total % 1000000007
	print(total)


bigmod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, a) = map(int, input().split())
	p = 1
	ans = 0
	for i in range(1, n + 1):
		a %= bigmod
		a *= p
		p = pow(a, 2 * i - 1, bigmod)
		ans += p
	print(ans % bigmod)


def pow(base, exp):
	if exp == 0:
		return 1
	half = pow(base, exp // 2) % MOD
	ans = half ** 2
	ans %= MOD
	if exp % 2:
		ans *= base
		ans %= MOD
	return ans
t = int(input())
MOD = 1000000007
while t:
	t -= 1
	(n, a) = input().split()
	(n, a) = (int(n), int(a))
	base = a
	ans = 0
	for i in range(1, n + 1):
		exp = 2 * i - 1
		pi = pow(base, exp)
		ans += pi
		ans %= MOD
		base *= pi
		base %= MOD
	print(ans)


import math
t = int(input())
MOD = 10 ** 9 + 7
for i in range(t):
	(n, a) = map(int, input().split())
	sums = 0
	for j in range(1, n + 1):
		prod = pow(a, 2 * j - 1, MOD)
		sums = (sums + prod) % MOD
		a = a * prod % MOD
	print(sums)


MOD = 1000000007

def moduloMultiplication(a, b, mod):
	res = 0
	a = a % mod
	while b:
		if b & 1:
			res = (res + a) % mod
		a = 2 * a % mod
		b >>= 1
	return res
for _ in range(int(input())):
	(n, a) = list(map(int, input().split()))
	total = 0
	i = 1
	for j in range(n):
		temp = pow(a, i, MOD)
		total = total + temp
		a = moduloMultiplication(a, temp, MOD)
		i = i + 2
	print(total % (10 ** 9 + 7))


for _ in range(int(input())):
	(n, s) = list(map(int, input().split()))
	(p, count) = (1, 0)
	for i in range(1, n + 1):
		c = pow(s, 2 * i - 1, 10 ** 9 + 7)
		s *= c
		s = s % (10 ** 9 + 7)
		count = (count + c) % (10 ** 9 + 7)
	print(count)


def main():
	(n, a) = map(int, input().split())
	tot = 0
	mod = 1000000007
	a %= mod
	p = 1
	for i in range(1, n + 1):
		a %= mod
		p %= mod
		a *= p % mod
		p = pow(a, 2 * i - 1, mod) % mod
		tot += p % mod
	print(int(tot % mod))
for _ in range(int(input())):
	main()


MOD = 1000000007

def fast_power(base, power):
	result = 1
	while power > 0:
		if power % 2 == 1:
			result = result * base % MOD
		power = power // 2
		base = base * base % MOD
	return result
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	ans = 0
	cou = 0
	for i in range(a):
		cou = fast_power(b, 2 * i + 1) % MOD
		ans += cou
		ans = ans % MOD
		b = b % MOD
		b = cou * b
	print(ans % (MOD + 7))


m = int(1000000000.0 + 7)
for _ in range(int(input())):
	(n, a) = map(int, input().split())
	j = 1
	ans = 0
	for i in range(1, n + 1):
		k = pow(a, 2 * i - 1, m)
		ans += k
		a = a * k % m
	print(ans % m)


MOD = 10 ** 9 + 7

def powerLL(x, n):
	result = 1
	while n:
		if n & 1:
			result = result * x % MOD
		n = int(n / 2)
		x = x * x % MOD
	return result
t = int(input())
for _ in range(t):
	(n, a) = [int(x) for x in input().split()]
	p = a
	ans = a
	for i in range(n - 1):
		p = powerLL(p, 2 * (i + 1))
		ans = (ans + powerLL(p, 2 * (i + 2) - 1)) % MOD
	print(ans % MOD)


import sys
from math import sqrt, gcd, log2, log10, floor, ceil, factorial
try:
	sys.stdin = open('F:\\ABHISHEK-FOLDER\\ABHI-CP\\input.txt', 'r')
	sys.stdout = open('F:\\ABHISHEK-FOLDER\\ABHI-CP\\output.txt', 'w')
except:
	pass
MOD = 10 ** 9 + 7
for _ in range(int(input())):
	(m, num) = [int(i) for i in input().split()]
	ans = num
	perv_elee = num
	prev_val = num
	for i in range(3, 2 * m, 2):
		curr_elee = prev_val * perv_elee % MOD
		curr_val = pow(curr_elee, i, MOD)
		ans = (ans + curr_val) % MOD
		prev_val = curr_val % MOD
		perv_elee = curr_elee % MOD
	ans %= MOD
	print(ans)


MOD = 10 ** 9 + 7
for _ in range(int(input())):
	(m, num) = [int(i) for i in input().split()]
	ans = num
	perv_elee = num
	prev_val = num
	for i in range(3, 2 * m, 2):
		curr_elee = prev_val * perv_elee % MOD
		curr_val = pow(curr_elee, i, MOD)
		ans = (ans + curr_val) % MOD
		prev_val = curr_val % MOD
		perv_elee = curr_elee % MOD
	ans %= MOD
	print(ans)


def po(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
m = 10 ** 9 + 7
for _ in range(int(input())):
	(n, a) = map(int, input().split())
	i = 1
	t = 1
	s = 0
	while n:
		n -= 1
		s += po(a, t, 10 ** 9 + 7)
		s %= m
		a = a * po(a, t, 10 ** 9 + 7)
		a %= m
		t += 2
	print(s % m)


mod = int(1000000000.0 + 7)
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	p = 0
	for i in range(1, n + 1):
		l = pow(k, 2 * i - 1, mod)
		p = (p + l) % mod
		k = k * l % mod
	print(p)


t = int(input())
for _ in range(t):
	(n, a) = map(int, input().split())
	(sum, p) = (0, a)
	mod = 1000000007
	for i in range(1, n + 1):
		next = pow(p, 2 * i - 1, mod)
		sum = (sum + next) % mod
		p = p * next % mod
	print(sum)


t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	p = 0
	m = int(1000000000.0 + 7)
	for i in range(1, n + 1):
		l = pow(k, 2 * i - 1, m)
		p += l
		p = p % m
		k = k * l % m
	print(p)


md = 1000000007

def power(a, n):
	a = a % md
	ans = 1
	while n > 0:
		if n & 1:
			ans = ans * a % md
		a = a * a % md
		n = n >> 1
	return ans
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	assignment = [0 for i in range(20)]
	l = [0 for i in range(n)]
	j = 1
	ans = 0
	a = 1
	l[0] = m
	abba = 3
	for i in range(1, n):
		m = m * l[i - 1] % 1000000007
		l[i] = pow(m, abba, md)
		abba += 2
		cid = [0 for i in range(10)]
		j += 2
	ans = 0
	kilo = 10
	for i in l:
		kilo += 1
		style = None
		ans = (ans % 1000000007 + i % 1000000007) % 1000000007
	print(ans % 1000000007)


k = 1000000007
t = int(input())
for _ in range(t):
	(n, a) = map(int, input().split())
	s = a
	x = a
	c = a
	for i in range(1, n):
		c = x * c % k
		x = c
		c = pow(c, 2 * i + 1, k)
		s = (s + c) % k
	print(s)


MOD = 10 ** 9 + 7

def power(x, y):
	if y == 0:
		return 1
	elif y == 1:
		return x
	else:
		R = power(x, y // 2)
		if y % 2 == 0:
			return R * R % MOD
		else:
			return R * x * R % MOD
tests = int(input())
for _ in range(tests):
	inputs = list(map(int, input().split(' ')))
	(n, a) = (inputs[0], inputs[1])
	totalSum = 0
	for i in range(n):
		removed = 2 * i + 1
		p = power(a, removed)
		totalSum += p
		a = power(a, removed + 1)
	print(totalSum % MOD)


t = int(input())
for i in range(t):
	(n, a) = map(int, input().split())
	ans = 0
	x = 1
	y = 1000000007
	for i in range(1, n + 1):
		a = x * a % y
		p = pow(a, 2 * i - 1, y)
		ans = (ans + p) % y
		x = p
	print(ans % y)


for _ in range(int(input())):
	(N, A) = [int(_) for _ in input().split()]
	x = 0
	for _ in range(N):
		c = pow(A, 2 * (_ + 1) - 1, 1000000007)
		x += c
		x %= 1000000007
		A *= c
		A %= 1000000007
	print(x % 1000000007)


import math
t = int(input())
for _ in range(t):
	(n, a) = map(int, input().split())
	p = 0
	mod = 10 ** 9 + 7
	for i in range(1, n + 1):
		p_i = pow(a, 2 * i - 1, mod)
		p = (p + p_i) % mod
		prod = p_i % mod
		a = a * prod % mod
	ans = p
	print(ans)


m = 10 ** 9 + 7

def power(x, y):
	if y == 0:
		return 1
	temp = power(x, y // 2)
	if y % 2 == 0:
		return temp * temp % m
	else:
		return x * temp * temp % m
for i in range(int(input())):
	(n, a) = map(int, input().split())
	i = 1
	res = 0
	while i <= n:
		p = power(a, 2 * i - 1)
		res += p
		a = a * p % m
		i += 1
	print(res % m)


MOD = 1000000007
for _ in range(int(input())):
	(n, a) = map(int, input().split())
	tot = 0
	p = 1
	for i in range(1, n + 1):
		a *= p % MOD
		a %= MOD
		p = pow(a, 2 * i - 1, MOD)
		tot += p % MOD
	print(tot % MOD)


m = 10 ** 9 + 7

def solve(n, a):
	return aid(n, a)

def mul(f, b):
	if f == 1:
		return b
	else:
		store = mul(f // 2, b)
		if f % 2 == 0:
			return store * store % m
		else:
			return store * store % m * b % m

def aid(n, a):
	(b, c) = (a * a, a)
	for i in range(1, n):
		d = mul(2 * i + 1, b)
		(b, c) = (d * b % m, (d + c) % m)
	return c
for _ in range(int(input())):
	print(solve(*map(int, input().split())))


bigmod = 10 ** 9 + 7
for _ in range(int(input())):
	(N, A) = map(int, input().split())
	p = 1
	ans = 0
	for i in range(0, N):
		A %= bigmod
		A *= p
		p = pow(A, 2 * i + 1, bigmod)
		ans += p
	print(ans % bigmod)


t = int(input())
m = 1000000007

def power(x, n):
	res = 1
	while n > 0:
		if n % 2 == 1:
			res = res * x % m
		x = x * x % m
		n = n // 2
	return res
for each_t in range(t):
	(n, a) = input().split()
	(n, a) = (int(n), int(a))
	pro = a
	res = 0
	for i in range(1, 2 * n, 2):
		temp = power(pro, i)
		pro = pro % m * (temp % m) % m
		res = (res % m + temp % m) % m
	print(res)


import math
m = int(1000000000.0 + 7)

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x
		y = y >> 1
		x = x * x % p
	return res
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = k
	l = k
	for i in range(1, n):
		s += power(power(l, 2 * i, m), 2 * i + 1, m)
		s = s % m
		l = power(l, 2 * i, m)
	print(s)


def power(b, e):
	a = 1
	while e > 0:
		if e % 2 == 1:
			a = a * b % 1000000007
		b = b * b % 1000000007
		e //= 2
	return a

def matrix(N, A):
	c = A
	s = 0
	for i in range(1, N + 1):
		p = power(c, 2 * i - 1)
		s += p
		c *= p
		if s > 1000000007:
			s %= 1000000007
		if c > 1000000007:
			c %= 1000000007
	return s
t = int(input())
for _ in range(t):
	(N, A) = map(int, input().split())
	ans = matrix(N, A)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	mod = 10 ** 9 + 7
	s = 0
	for i in range(1, n + 1):
		p = pow(k, 2 * i - 1, mod)
		s = (s + p) % mod
		k = p * k % mod
	print(s)


import math

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
t = int(input())
for i in range(t):
	(n, a) = map(int, input().split())
	s = 0
	x = a
	m = 1000000007
	for j in range(1, n + 1):
		x = power(a, 2 * j - 1, m)
		a = a % m * x % m % m
		s = (s % m + x % m) % m
	print(s)


for _ in range(int(input())):
	ans = 0
	odd = 1
	(a, b) = map(int, input().split())
	for i in range(a):
		x = pow(b, odd, 1000000007)
		ans += x
		b = b * x
		b = b % 1000000007
		odd += 2
	print(ans % 1000000007)


for testCase in range(int(input())):
	(n, a) = list(map(int, input().split()))
	p = 1
	sump = 0
	for i in range(1, n + 1):
		p = pow(a, 2 * i - 1, 1000000007)
		sump += p
		a = a * p % 1000000007
	print(sump % (10 ** 9 + 7))


MOD = 1000000007
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	ans = 0
	cou = 0
	for i in range(a):
		cou = pow(b, 2 * i + 1, MOD)
		ans += cou
		ans = ans % MOD
		b = b % MOD
		b = cou * b
	print(ans % (MOD + 7))


f = 1000000007
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	t = 0
	for i in range(0, n):
		t = t + pow(m % f, (2 * i + 1) % f, 1000000007) % 1000000007
		m = m * pow(m % f, (2 * i + 1) % f, 1000000007) % 1000000007
	print(t % 1000000007)


mod = 1000000007

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
for iq in range(int(input())):
	(n, a) = list(map(int, input().split()))
	result = 0
	for i in range(1, n + 1):
		p = power(a, 2 * i - 1, mod)
		result = (result + p) % mod
		a = a * p % mod
	print(result)


try:
	import sys
	sys.setrecursionlimit(1500)
	N = 1000000007

	def exponentiation(bas, exp):
		if exp == 0:
			return 1
		if exp == 1:
			return bas % N
		t = exponentiation(bas, int(exp / 2))
		t = t * t % N
		if exp % 2 == 0:
			return t
		else:
			return bas % N * t % N
	t = int(input())
	for i in range(0, t):
		(n, a) = map(int, input().split(' '))
		c = 0
		l = 0
		for i in range(1, n + 1):
			k = 2 * i - 1
			op = exponentiation(a, k)
			l += op
			l %= N
			a *= op
			a %= N
		print(l % N)
except:
	pass


MOD = 1000000007

def power(x, y):
	res = 1
	x = x % MOD
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % MOD
		y = y >> 1
		x = x * x % MOD
	return res
for _ in range(int(input())):
	(N, A) = list(map(int, input().split()))
	op = 0
	if A == 1:
		print(1)
		continue
	i = 1
	for _ in range(N):
		p = power(A, i)
		i += 2
		op = (op + p) % MOD
		A = A * p % MOD
	print(op)


import math

def power(a, p, mod=math.inf):
	if p == 0:
		return 1
	if p == 1:
		return a
	R = power(a, p // 2, mod) % mod
	if p % 2 == 0:
		return R * R % mod
	else:
		return R * R * a % mod
mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(N, A) = map(int, input().split())
	res = 0
	prev = 1
	curr = A
	for i in range(N):
		temp = power(prev * curr, 2 * i + 1, mod)
		res += temp
		res %= mod
		prev *= curr
		prev %= mod
		curr = temp % mod
	print(res % mod)


t = int(input())
for _ in range(t):
	(n, a) = map(int, input().split())
	sum1 = 0
	next1 = a
	for i in range(n):
		power = 2 * i + 1
		prod = pow(a, power, 1000000007)
		sum1 = sum1 + prod
		a = a * prod
		a = a % 1000000007
	print(sum1 % 1000000007)