402202: GYM100694 L Hanoi Towers and the Progress

Andrey doesn't like Hanoi — for hundreds of years the highest buildings there are three ancient towers, and every year giant rings are moved from one tower to another using the same algorithm (see Notes section). Every year Andrey suffers from the fact that a huge amount of money is spent on such weird amusement — really, why do they move these rings with the help of lots of cranes, blocking the city center for several days? But the progress moves forward, and in the next year k additional small towers will be built in Hanoi. These towers won't be able to hold more than one ring. Having read this, Andrey immediately became interested in the minimal number of turns required to move n rings between big towers after this innovation. He doesn't want to spend even a second on this city, so it's your task to do these calculations.

The only line contains two space-separated integers n and k (1 ≤ n ≤ 10⁹, 0 ≤ k ≤ 10⁹) — the number of rings and the number of additional towers (the total number of towers will be k + 3).

Output the minimal number of turns to move all rings from one big tower to another. As this number can be too large, output its remainder of division by 10⁹ + 7.

3 0

7

3 1

5

42 0

46480317

1000 0

688423209

«Hanoi towers» is the puzzle with three rods («towers»). At the beginning there are some rings on one of these rods, all of them have different size, and the smaller rings lie higher. The task is to move all the rings to another rod. In one turn the player can move one ring from the top of one rod to the top of another rod, and it's prohibited to put the larger ring onto the smaller one.