403545: GYM101192 G ReHanoi Towers
Memory Limit：64 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
G. ReHanoi Towerstime limit per test1 secondmemory limit per test64 megabytesinputstandard inputoutputstandard output1 ≤ n ≤ 109 Output
Everybody knows the classical puzzle about Hanoi Towers. There are three rods and one of them has n rings in ascending order of radius, the biggest disk is at the bottom, smallest is at the top. The objective of the puzzle is to move all of the rings to another rod in a minimal number of steps and preserve the disk order. During one step you are allowed to move only one ring and smaller radius rings can only be put on top of bigger radius rings.
You are required to solve modified Hanoi Towers puzzle. You have four rods instead of three. All other rules are left unchanged.
InputA single integer number n — the number of rings on the first rod.
The minimal number of steps modulo 109 + 7.
ExamplesInput2Output
3Input
8Output
33