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: VERY_HARD
Tags: Matrices

Dynamic programming

Mathematics
Skill types: Dynamic programming

Starter code:

Solutions:
try:
	from cp import input, setInputFile
except:
	pass
import math
import copy
import numpy as np
import sys

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

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)
for _ in range(int(input())):
	main()


import sys
MOD = 1000000007

def multiply(m1):
	a = m1[0][0] * m1[0][0] + m1[0][1] * m1[1][0]
	b = m1[0][0] * m1[0][1] + m1[0][1] * m1[1][1]
	c = m1[1][0] * m1[0][0] + m1[1][1] * m1[1][0]
	d = m1[1][0] * m1[0][1] + m1[1][1] * m1[1][1]
	m1[0][0] = a % MOD
	m1[0][1] = b % MOD
	m1[1][0] = c % MOD
	m1[1][1] = d % MOD

def solve(n, m):
	m = m % MOD
	if n == 1:
		return m
	if n == 2:
		return m ** 2 % MOD
	if m == 1:
		return 0
	mat = [[m - 1, m - 1], [1, 0]]
	res = [m ** 2 % MOD, m]
	n -= 2
	while n:
		if n % 2:
			t0 = res[0]
			res[0] = (mat[0][0] * res[0] + mat[0][1] * res[1]) % MOD
			res[1] = (mat[1][0] * t0 + mat[1][1] * res[1]) % MOD
			n -= 1
		else:
			multiply(mat)
			n >>= 1
	return res[0]
t = int(sys.stdin.readline())
for _ in range(t):
	(n, m) = map(int, sys.stdin.readline().split())
	sys.stdout.write('{}\n'.format(solve(n, m)))


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)


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)


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

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
		M = M ** (n - 1)
		B = M * 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)


import sys

def multiply(matrix1, matrix2, mod):
	ans = [[-1 for i in range(len(matrix2[0]))] for _ in range(len(matrix1))]
	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
	return ans

def power(a, b, mod):
	res = [[1, 0], [0, 1]]
	for i in range(len(a)):
		for j in range(len(a[0])):
			a[i][j] = a[i][j] % mod
	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]]
	ans = power(a, n - 1, mod)
	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)


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)


import sys
PRIME = 1000000007

def multiply(m1):
	a = m1[0][0] * m1[0][0] + m1[0][1] * m1[1][0]
	b = m1[0][0] * m1[0][1] + m1[0][1] * m1[1][1]
	c = m1[1][0] * m1[0][0] + m1[1][1] * m1[1][0]
	d = m1[1][0] * m1[0][1] + m1[1][1] * m1[1][1]
	m1[0][0] = a % PRIME
	m1[0][1] = b % PRIME
	m1[1][0] = c % PRIME
	m1[1][1] = d % PRIME
t = int(sys.stdin.readline())
for _ in range(t):
	(n, m) = map(int, sys.stdin.readline().split())
	m = m % PRIME
	if n == 1:
		sys.stdout.write('{}\n'.format(m))
	elif n == 2:
		sys.stdout.write('{}\n'.format(m ** 2 % PRIME))
	elif m == 1:
		sys.stdout.write('{}\n'.format(0))
	else:
		mat = [[m - 1, m - 1], [1, 0]]
		ans = [m ** 2 % PRIME, m]
		n -= 2
		while n:
			if n % 2 == 1:
				t0 = ans[0]
				ans[0] = (mat[0][0] * ans[0] + mat[0][1] * ans[1]) % PRIME
				ans[1] = (mat[1][0] * t0 + mat[1][1] * ans[1]) % PRIME
				n -= 1
			else:
				multiply(mat)
				n >>= 1
		sys.stdout.write('{}\n'.format(ans[0]))


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)