You are given two integers $N$ and $M$. Find the number of sequences $A_1, A_2, \ldots, A_N$, where each element is an integer between $1$ and $M$ (inclusive) and no three consecutive elements are equal. 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 $M$.

-----Output-----
For each test case, print a single line containing one integer ― the number of valid sequences modulo $10^9+7$.

-----Constraints-----
- $1 \le T \le 10^5$
- $1 \le N, M \le 10^{18}$

-----Subtasks-----
Subtask #1 (50 points):
- $T \le 20$
- $N \le 10^5$
Subtask #2 (50 points): original constraints

-----Example Input-----
2 
2 2
3 4

-----Example Output-----
4
60

Difficulty: interview

Starter code:

Solutions:
import sys
def fin(): return sys.stdin.readline().strip()
def fout(s, end="\n"): sys.stdout.write(str(s)+end)

MOD = pow(10, 9)+7
t = int(input())
while t>0:
 t -= 1
 n, m = list(map(int, fin().split()))
 if n == 1:
  print(m%MOD)
  continue
 dp1 = m*(m-1)
 dp2 = m
 for i in range(3, n+1):
  temp = dp2
  dp2 = dp1 
  dp1 = (temp*(m-1))%MOD+(dp1*(m-1))%MOD
 print((dp1+dp2)%MOD)

 



# cook your dish her
try:from cp import input,setInputFile
except:pass
import math 
import copy
# import random
import numpy as np
import sys
# import time
def input(): return sys.stdin.readline()
def itarr(arr): return list(range(len(arr)))
def mp():return list(map(int,input().split()))
def lmp():return list(map(int,input().split()))
def inp():return int(input())
MOD=1000000007
# from functools import lru_cach
def mexp(m,p):
 if p==1:
  return m%MOD
 x=(m%MOD * m%MOD )%MOD
 r=mexp(x%MOD,p//2)
 if p%2==0:
  return r%MOD
 else:
  return (m%MOD*r%MOD)%MOD

def main():
 n,b=mp()
 t=b%MOD
 g=(b*b)%MOD
 n%=MOD
 if n==2:
  print(g)
  return 
 if n==1:
  print(t)
  return

 MI=np.matrix(np.array([[(b-1)%MOD,(b-1)%MOD],[1,0]]))

 arr= mexp(MI,n-2) 
 arr=np.array(arr)
 ans = (arr[0][0]*g)%MOD + (arr[0][1]*t)%MOD
 ans%=MOD
 print(ans)


 
 

# main()

for _ in range(int(input())):
 main()
 # break





t=int(input())
mod=10**9+7
for _ in range(t):
 n,m=map(int,input().split())
 same=[0]
 diff=[m]
 for i in range(n-1):
  s=diff[-1]
  d=(same[-1]+diff[-1])*(m-1)
  same+=[s%mod]
  diff+=[d%mod]
 print((same[-1]+diff[-1])%mod)

"""
-----------------------------Pseudo---------------------------------
"""
import copy
import sys
from collections import defaultdict, Counter

def input(): return sys.stdin.readline()
def mapi(): return map(int,input().split())
def maps(): return map(str,input().split())
#
def print(arg, *argv, end=None):
 sys.stdout.write(str(arg))
 for i in argv: sys.stdout.write(" "+str(i))
 sys.stdout.write(end) if end else sys.stdout.write("\n")

#---------------------------------------------------------------#


mod = 1000000007

class Matrix(object):
 def __init__(self, rows,cols):
  self.rows = rows
  self.cols = cols
  self.mat = [[0]*cols for i in range(rows)]

 def __len__(self):
  return len(self.mat)

 def __getitem__(self, key1):
  return self.mat[key1]

 def __setitem__(self, key1, value):
  self.mat[key1] = value

 def __str__(self):
  res = ""
  for i in self.mat:
   res+=" ".join(str(j) for j in i)+"\n"
  return res[:-1]

 def __mul__(self, other):
  if len(other) != len(self.mat[0]):
   print("matrices are not compitable for multiplication")
   return
  res = Matrix(len(self.mat), len(other[0]))
  for i in range(self.rows):
   for j in range(len(other[0])):
    ans = 0
    for k in range(len(other)):
     ans += self.mat[i][k]*other[k][j]%mod
    res[i][j] = ans%mod
  return res
 """
    def __pow__(self, n):
     if n==0 or n==1:
      return self
     tmp = self
     #copy.deepcopy(self)
     tmp = tmp**(n//2)
     #print(tmp)
     tmp = tmp*tmp
     if(n%2 != 0):
      tmp = tmp*self
     return tmp
    """
 def __pow__(self,n):
  res = Matrix(self.rows, self.rows)
  tmp = self
  for i in range(self.rows):
   res[i][i] = 1
  while n>0:
   if n&1:
    res = res*tmp
   n>>=1
   tmp = tmp*tmp
  return res
"""
dp[1] = m
dp[2] = m^2
dp[3] = m^3-m
recurrent relation:  dp[i] = m*dp[i-1] - (m-1)*dp[i-3]

"""
def solve():
 t = 1
 t = int(input())
 while(t):
  t-=1
  n,m = mapi()
  m%=mod
  B = Matrix(3,1)
  M = Matrix(3,3)
  B[0][0] = m
  B[1][0] = (m*m)%mod
  B[2][0] = ((m*m%mod +mod -1)%mod)*m%mod

  M[0][1] = 1
  M[1][2] = 1
  M[2][0] = (mod-m+1)%mod
  M[2][1] = 0
  M[2][2] = m
  #print(M)
  M = M**(n-1)
  B = M*B
  #print(B)
  print(B[0][0])

#---------------------------------------------------------------#
def __starting_point():
 solve()


__starting_point()

def multiply(F,M,i):
 x = (F[0][0]*M[0][0]+F[1][0]*M[0][1])%i
 y = (F[0][0]*M[1][0]+F[1][0]*M[1][1])%i
 z = (F[0][1]*M[0][0]+F[1][1]*M[0][1])%i
 w = (F[0][1]*M[1][0]+F[1][1]*M[1][1])%i
 F[0][0] = x
 F[1][0] = y
 F[0][1] = z
 F[1][1] = w
def power(F,M,n,i):
 if(n<2): return
 power(F,M,n//2,i)
 multiply(F,F,i)
 if(n%2!=0): multiply(F,M,i)
for t in range(0,int(input())):
 i = 1000000007;
 n,m = map(int, input().split())
 F = [[(m-1)%i,1],[(m-1)%i,0]]
 M = [[(m-1)%i,1],[(m-1)%i,0]]
 if(n==1): i = m%i
 elif(n==2): i = (m*m)%i
 else:
  power(F,M,n-2,i)
  i = ((F[0][0]*m+F[1][0])*m)%i
 print(i)

for t in range(0,int(input())):
 z = 1000000007;
 ar = [int(i) for i in input().split(" ")]
 if(ar[0]==1): print(ar[1]%z)
 else:
  a = ar[1]%z
  b = ((ar[1]%z)*(ar[1]%z))%z
  c = (ar[1]-1)%z
  for i in range(2,ar[0]):
   d = (c*(b+a))%z
   a = b
   b = d
  print(b)

mod = 10**9 + 7
for _ in range(int(input())):
 n, m = list(map(int,input().split()))
 if n == 1:
  print(m%mod)
  continue
 if n == 2:
  print((m%mod)*(m%mod)%mod)
  continue
 if m == 1:
  print(0)
  continue

 t = 0

 t1 = m%mod
 t2 = ((m%mod)*(m%mod)%mod)
 for i in range(3, n+1):
  t = ((t1+t2)%mod * (m-1)%mod)%mod
  t1 = t2
  t2 = t
 print(t)


import sys
def multiply(matrix1,matrix2,mod):
 ans=[[-1 for i in range(len(matrix2[0]))] for _ in range(len(matrix1))]
 #print(ans,'before')
 for i in range(len(matrix1)):
  for j in range(len(matrix2[0])):
   s=0
   k=0
   while k<len(matrix1[0]):
    s+=(matrix1[i][k]*matrix2[k][j])%mod
    k+=1
   ans[i][j]=(s%mod)
 #print(ans,'ans')
 return ans
def power(a,b,mod):
 res=[[1,0],[0,1]]
 #print(res,'res')
 for i in range(len(a)):
  for j in range(len(a[0])):
   a[i][j]=a[i][j]%mod
 #print(a,'a')
 while b>0:
  if (b&1):
   res=multiply(res,a,mod)
  b=b>>1
  a=multiply(a,a,mod)
 return res
t=int(sys.stdin.readline())
mod=10**9+7
for _ in range(t):
 n,m=list(map(int,sys.stdin.readline().split()))
 base=[[m],[0]]
 a=[[m-1,m-1],[1,0]]
 #print(base,'base')
 #print(a,'a')
 ans=power(a,n-1,mod)
 #print(ans,'ans')
 ans=multiply(ans,base,mod)
 print((ans[0][0]+ans[1][0])%mod)
 
   


t = int(input())
for _ in range(t):
 mod = 10**9+7
 n,m = [int(c) for c in input().split(' ')]
 if n==1:
  print(m%mod)
  continue
 a,b = m*(m-1),m
 if n==2:
  print((a+b)%mod)
 else:
  for p in range(3,n+1):
   temp = a
   a = (a%mod+b%mod)%mod
   a = (a*(m-1))%mod
   b = temp
  print((a+b)%mod)