Neil and his Binary Tree solution codechef

For Solution
Click Here!
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 64bit 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 spaceseparated 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
 1≤T≤1001≤T≤100
 1≤M≤10001≤M≤1000
 1≤N<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.

For Solution
Click Here!