You have found $M$ different types of jewels in a mine and each type of jewel is present in an infinite number.
There are $N$ different boxes located at position $(1 ,2 ,3 ,...N)$.
Each box can collect jewels up to a certain number ( box at position $i$ have $i$ different partitions and each partition can collect at most one jewel of any type).
Boxes at odd positions are already fully filled with jewels while boxes at even positions are completely empty.
Print the total number of different arrangements possible so that all boxes can be fully filled.
As the answer can be very large you can print it by doing modulo with 1000000007(10^9+7).

-----Input:-----
- First line will contain $T$, number of testcases. 
- Each testcase contains of a single line of input, two integers $N ,  M$. 

-----Output:-----
For each testcase, Print the total number of different arrangement.

-----Constraints-----
- $1 \leq T \leq 20000$
- $1 \leq N \leq 1e9$
- $1 \leq M \leq 1e14$

-----Sample Input:-----
2
1 10
5 2

-----Sample Output:-----
1
64

```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 = '\'\'\'\r\n      ___           ___                         ___                       ___           ___                         ___\r\n     /\\__\\         /\\  \\         _____         /\\  \\                     /\\  \\         /\\  \\                       /\\__\\\r\n    /:/ _/_        \\:\\  \\       /::\\  \\        \\:\\  \\       ___         /::\\  \\       |::\\  \\         ___         /:/ _/_\r\n   /:/ /\\  \\        \\:\\  \\     /:/\\:\\  \\        \\:\\  \\     /\\__\\       /:/\\:\\__\\      |:|:\\  \\       /\\__\\       /:/ /\\  \\\r\n  /:/ /::\\  \\   ___  \\:\\  \\   /:/  \\:\\__\\   ___ /::\\  \\   /:/__/      /:/ /:/  /    __|:|\\:\\  \\     /:/  /      /:/ /::\\  \\\r\n /:/_/:/\\:\\__\\ /\\  \\  \\:\\__\\ /:/__/ \\:|__| /\\  /:/\\:\\__\\ /::\\  \\     /:/_/:/__/___ /::::|_\\:\\__\\   /:/__/      /:/_/:/\\:\\__\\\r\n \\:\\/:/ /:/  / \\:\\  \\ /:/  / \\:\\  \\ /:/  / \\:\\/:/  \\/__/ \\/\\:\\  \\__  \\:\\/:::::/  / \\:\\~~\\  \\/__/  /::\\  \\      \\:\\/:/ /:/  /\r\n  \\::/ /:/  /   \\:\\  /:/  /   \\:\\  /:/  /   \\::/__/       ~~\\:\\/\\__\\  \\::/~~/~~~~   \\:\\  \\       /:/\\:\\  \\      \\::/ /:/  /\r\n   \\/_/:/  /     \\:\\/:/  /     \\:\\/:/  /     \\:\\  \\          \\::/  /   \\:\\~~\\        \\:\\  \\      \\/__\\:\\  \\      \\/_/:/  /\r\n     /:/  /       \\::/  /       \\::/  /       \\:\\__\\         /:/  /     \\:\\__\\        \\:\\__\\          \\:\\__\\       /:/  /\r\n     \\/__/         \\/__/         \\/__/         \\/__/         \\/__/       \\/__/         \\/__/           \\/__/       \\/__/\r\n\r\n\'\'\'\r\n"""\r\n░░██▄░░░░░░░░░░░▄██\r\n░▄▀░█▄░░░░░░░░▄█░░█░\r\n░█░▄░█▄░░░░░░▄█░▄░█░\r\n░█░██████████████▄█░\r\n░█████▀▀████▀▀█████░\r\n▄█▀█▀░░░████░░░▀▀███\r\n██░░▀████▀▀████▀░░██\r\n██░░░░█▀░░░░▀█░░░░██\r\n███▄░░░░░░░░░░░░▄███\r\n░▀███▄░░████░░▄███▀░\r\n░░░▀██▄░▀██▀░▄██▀░░░\r\n░░░░░░▀██████▀░░░░░░\r\n░░░░░░░░░░░░░░░░░░░░\r\n"""\r\nimport sys\r\nimport math\r\nimport collections\r\nimport operator as op\r\nfrom collections import deque\r\nfrom math import gcd, inf, sqrt, pi, cos, sin, ceil, log2, floor, log\r\nfrom bisect import bisect_right, bisect_left, bisect\r\n\r\n# sys.stdin = open(\'input.txt\', \'r\')\r\n# sys.stdout = open(\'output.txt\', \'w\')\r\n\r\nfrom functools import reduce\r\nfrom sys import stdin, stdout, setrecursionlimit\r\nsetrecursionlimit(2**20)\r\n\r\n\r\ndef ncr(n, r):\r\n    r = min(r, n - r)\r\n    numer = reduce(op.mul, list(range(n, n - r, -1)), 1)\r\n    denom = reduce(op.mul, list(range(1, r + 1)), 1)\r\n    return numer // denom  # or / in Python 2\r\n\r\n\r\ndef prime_factors(n):\r\n    i = 2\r\n    factors = []\r\n    while i * i <= n:\r\n        if n % i:\r\n            i += 1\r\n        else:\r\n            n //= i\r\n            factors.append(i)\r\n    if n > 1:\r\n        factors.append(n)\r\n    return (list(factors))\r\n\r\n\r\ndef isPowerOfTwo(x):\r\n    return (x and (not(x & (x - 1))))\r\n\r\nMOD = 1000000007  # 10^9 + 7\r\nPMOD = 998244353\r\nN = 10**18 + 1\r\nLOGN = 30\r\nalp = \'abcdefghijklmnopqrstuvwxyz\'\r\nT = 1\r\nT = int(stdin.readline())\r\nfor _ in range(T):\r\n    n, m = list(map(int, stdin.readline().rstrip().split()))\r\n    # n = int(stdin.readline())\r\n    # a = list(map(int, stdin.readline().rstrip().split()))\r\n    # b = list(map(int, stdin.readline().rstrip().split()))\r\n    # s = str(stdin.readline().strip(\'\\n\'))\r\n    # s = list(stdin.readline().strip(\'\\n\'))\r\n    # m = int(stdin.readline())\r\n    # c = list(map(int, stdin.readline().rstrip().split()))\r\n    p = (n * (n + 1)) // 2 - (ceil(n / 2))**2\r\n    print(pow(m, p, MOD))\r\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14339