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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '"""\n-----------------------------Pseudo---------------------------------\n"""\nimport copy\nimport sys\nfrom collections import defaultdict, Counter\n\ndef input(): return sys.stdin.readline()\ndef mapi(): return map(int,input().split())\ndef maps(): return map(str,input().split())\n#\ndef print(arg, *argv, end=None):\n sys.stdout.write(str(arg))\n for i in argv: sys.stdout.write(" "+str(i))\n sys.stdout.write(end) if end else sys.stdout.write("\\n")\n\n#---------------------------------------------------------------#\n\n\nmod = 1000000007\n\nclass Matrix(object):\n def __init__(self, rows,cols):\n  self.rows = rows\n  self.cols = cols\n  self.mat = [[0]*cols for i in range(rows)]\n\n def __len__(self):\n  return len(self.mat)\n\n def __getitem__(self, key1):\n  return self.mat[key1]\n\n def __setitem__(self, key1, value):\n  self.mat[key1] = value\n\n def __str__(self):\n  res = ""\n  for i in self.mat:\n   res+=" ".join(str(j) for j in i)+"\\n"\n  return res[:-1]\n\n def __mul__(self, other):\n  if len(other) != len(self.mat[0]):\n   print("matrices are not compitable for multiplication")\n   return\n  res = Matrix(len(self.mat), len(other[0]))\n  for i in range(self.rows):\n   for j in range(len(other[0])):\n    ans = 0\n    for k in range(len(other)):\n     ans += self.mat[i][k]*other[k][j]%mod\n    res[i][j] = ans%mod\n  return res\n """\n    def __pow__(self, n):\n     if n==0 or n==1:\n      return self\n     tmp = self\n     #copy.deepcopy(self)\n     tmp = tmp**(n//2)\n     #print(tmp)\n     tmp = tmp*tmp\n     if(n%2 != 0):\n      tmp = tmp*self\n     return tmp\n    """\n def __pow__(self,n):\n  res = Matrix(self.rows, self.rows)\n  tmp = self\n  for i in range(self.rows):\n   res[i][i] = 1\n  while n>0:\n   if n&1:\n    res = res*tmp\n   n>>=1\n   tmp = tmp*tmp\n  return res\n"""\ndp[1] = m\ndp[2] = m^2\ndp[3] = m^3-m\nrecurrent relation:  dp[i] = m*dp[i-1] - (m-1)*dp[i-3]\n\n"""\ndef solve():\n t = 1\n t = int(input())\n while(t):\n  t-=1\n  n,m = mapi()\n  m%=mod\n  B = Matrix(3,1)\n  M = Matrix(3,3)\n  B[0][0] = m\n  B[1][0] = (m*m)%mod\n  B[2][0] = ((m*m%mod +mod -1)%mod)*m%mod\n\n  M[0][1] = 1\n  M[1][2] = 1\n  M[2][0] = (mod-m+1)%mod\n  M[2][1] = 0\n  M[2][2] = m\n  #print(M)\n  M = M**(n-1)\n  B = M*B\n  #print(B)\n  print(B[0][0])\n\n#---------------------------------------------------------------#\ndef __starting_point():\n solve()\n\n\n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 181611