Neil and his Binary Tree solution codechef
Neil has a perfect binary tree with nodes, and an integer . 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 .
- 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.
Note: Neil and his Binary Tree solution codechef
- The root of the tree is at layer .
- 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 – the number of test cases. The test cases then follow.
- The only line of each test case contains two space-separated integers and – 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.
- It is guaranteed you can make a perfect binary tree with exactly nodes.
Sample Input 1 Neil and his Binary Tree solution codechef
1 3 3
Sample Output 1
- Test case : Here are all the possible assignments.