Teleport Travel
Time limit1sMemory limit1024 MB
A perfect binary tree of height N is given; starting from node 2K-1, find the minimum number of teleports needed to visit every node, taken modulo 1e9+7.
- Level
Hard8 of 10
- Topics
- Tree, Dynamic programming, Math, Combinatorics
- Solved
- No attempts yet
Problem
Mingyeom has decided to travel a perfect binary tree of height N. A perfect binary tree of height N is a perfect binary tree in which moving from the root node to any leaf node takes at least N - 1 moves. Every node has a number: the root node is node 1, and for every internal node (a node that is not a leaf) numbered P, its left child is node P × 2 and its right child is node P × 2 + 1.
The figure below shows an example of a perfect binary tree of height 4.
Mingyeom has arrived at some node for the trip. Mingyeom can walk from the node he is at to an adjacent node connected to it. However, Mingyeom never visits a node he has already visited again. Realizing that this may make it impossible to visit every node, Mingyeom prepared a teleporter. The teleporter sends Mingyeom to any node he has not visited. But every teleport costs a huge amount of money, so Mingyeom wants to minimize the number of teleports.
Given the number of the node where Mingyeom starts his trip, find the minimum number of teleports Mingyeom must make in order to visit every node.
Input
The height N of the perfect binary tree (1 ≤ N ≤ 3,000) and an integer K (1 ≤ K ≤ N) are given. Mingyeom starts his trip at node 2K - 1.
Output
Print the minimum number of teleports Mingyeom must make until he visits every node. Since the answer can be very large, print the answer modulo 109 + 7.