Neil and his Binary Tree solution codechef- 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.

Neil and his Binary Tree solution codechef

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

  • 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.

1-2-2

1-2-3

1-3-2

1-3-3

2-3-3

Leave a Comment

Your email address will not be published.