Contents

• # For Solution

Neil has a perfect binary tree with NN nodes, and an integer MM. 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 MM.
• 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 109+7109+7.

Note: Neil and his Binary Tree solution codechef

• The root of the tree is at layer 11.
• 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 Neil and his Binary Tree solution codechef

• The first line of each input contains TT – the number of test cases. The test cases then follow.
• The only line of each test case contains two space-separated integers NN and MM – the number of nodes on the tree and the maximum value of any node.

### Neil and his Binary Tree solution codechef Output Format

For each test case, output on a single line the number of different assignment modulo 109+7109+7.

### Constraints

• 1T1001≤T≤100
• 1M10001≤M≤1000
• 1N<2591≤N<259
• It is guaranteed you can make a perfect binary tree with exactly NN nodes.

### Sample Input 1  Neil and his Binary Tree solution codechef

1
3 3


### Sample Output 1

5


### Explanation

• Test case 11: Here are all the possible assignments.