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:

Difficulty: interview

Starter code:

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



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



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



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)

  
  


 



 


# cook your dish here
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)

m = int(1e9 + 7)
for _ in range(int(input())):
 n , a = list(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=int(1e9+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())
while t>0:
 t-=1
 n,k=list(map(int,input().split()))
 p=0
 m=int(1e9+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) 


# cook your dish here
z=int(1e9+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)

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):
  bc=pow(l,(2*j)-1,kp)
  ans=(bc+ans)%kp
  l=(l*bc)%kp
 print(ans)
  
'''511620149'''

'''def pow1(ap,op):
    if op==0:
     return 1 
    elif op%2==0:
     y=pow1(ap,op/2)
     return y*y   
    else:
     y=pow1(ap,op-1)
     return ap*y '''
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)

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

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

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)


# cook your dish here
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 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)
  a=((a*t_1)%mod)
  c+=2
 
 print(ans%mod)

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)

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)

# cook your dish here
test=int(input())
m=pow(10,9)+7
for _ in range(test):
 n,a=map(int,input().split())
 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)

t = int(input())
m = pow(10,9)+7
while t>0:
 n,a = map(int,input().split())
 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)
 t = t-1

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)

  # print(pi)
  ans += pi
  ans %= MOD
 
  base *= pi
  base %= MOD

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