Neil has a [perfect binary tree] with N nodes, and an integer M. He can assign values to nodes. He calls the tree good if the following conditions are met:
Nodes' values are positive integers no more than M.
Nodes at even levels have values strictly more than their parents' values.
Nodes at odd levels have values strictly less than their parents's values.

How many ways can Neil assign values to all nodes to get a good perfect binary tree? Since the answer can be large, please output it under modulo 10^{9} + 7.

Note:
The root of the tree is at layer 1.
Two assignments are different if there is at least one node with different values in both assignments.
You may need to use 64-bit data types in your programming language to take input.

------ Input Format ------ 

- The first line of each input contains T - the number of test cases. The test cases then follow.
- The only line of each test case contains two space-separated integers N and M - the number of nodes on the tree and the maximum value of any node.

------ Output Format ------ 

For each test case, output on a single line the number of different assignment modulo 10^{9} + 7.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ M ≤ 1000$
$1 ≤ N < 2^{59}$
- It is guaranteed you can make a perfect binary tree with exactly $N$ nodes.

----- Sample Input 1 ------ 
1
3 3

----- Sample Output 1 ------ 
5
----- explanation 1 ------ 
- Test case $1$: Here are all the possible assignments.

![1-2-2]

![1-2-3]

![1-3-2]

![1-3-3]

![2-3-3]

Difficulty: VERY_HARD
Tags: Dynamic programming

Range queries
Skill types: Dynamic programming

Range queries

Starter code:

Solutions:
from sys import stdin
input = stdin.readline
mod = 10 ** 9 + 7

def add(a, b):
	return (a % mod + b % mod) % mod

def mul(a, b):
	return a % mod * (b % mod) % mod

def sub(a, b):
	return (a - b + mod) % mod

def answer():
	for i in range(60):
		if n >> i & 1:
			x = i
	dp = [0 for j in range(m + 1)]
	for i in range(1, m + 1):
		dp[i] = 1
	for i in range(x - 1, -1, -1):
		prefix = [0 for j in range(m + 1)]
		for j in range(1, m + 1):
			prefix[j] = add(prefix[j - 1], dp[j])
		for j in range(1, m + 1):
			if i & 1 == 0:
				this = sub(prefix[m], prefix[j])
				dp[j] = mul(this, this)
			else:
				this = prefix[j - 1]
				dp[j] = mul(this, this)
	ans = 0
	for j in range(1, m + 1):
		ans = add(ans, dp[j])
	return ans
for T in range(int(input())):
	(n, m) = map(int, input().split())
	print(answer())


MOD = int(10 ** 9) + 7

def solve(N, M):
	height = 0
	while N > 0:
		height += 1
		N = N // 2
	dp = [[0 for i in range(0, M + 1)] for j in range(0, height + 1)]
	for j in range(1, M + 1):
		dp[1][j] = 1
	for i in range(2, height + 1):
		if i & 1 == 0:
			sum = 0
			for j in range(1, M + 1):
				dp[i][j] += sum * sum
				sum += dp[i - 1][j]
				dp[i][j] %= MOD
				sum %= MOD
		else:
			sum = 0
			for j in range(M, 0, -1):
				dp[i][j] += sum * sum
				sum += dp[i - 1][j]
				dp[i][j] %= MOD
				sum %= MOD
	ans = 0
	for i in range(1, M + 1):
		ans += dp[height][i]
		ans %= MOD
	print(ans)
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	solve(N, M)


import numpy as np
mod = 10 ** 9 + 7

def solve(n, m):
	if n == 1:
		return m
	if m == 1:
		return 0
	layers = n.bit_length()
	f = np.ones((layers, m + 1), dtype=int)
	g = np.ones((layers, m + 1), dtype=int)
	for ly in range(1, layers):
		cumsums = f[ly - 1][1:m].cumsum() % mod
		g[ly][2:m + 1] = cumsums * cumsums % mod
		cumsums = g[ly - 1][m:1:-1].cumsum() % mod
		f[ly][m - 1:0:-1] = cumsums * cumsums % mod
	result = np.sum(f[-1][1:m]) % mod
	return result
T = int(input())
for _ in range(T):
	(n, m) = [int(x) for x in input().split()]
	result = solve(n, m)
	print(result)