The Towers of Hanoi is a classic recursion problem:

N disks, of size N through 1, are stacked in order on the left post of three posts, so the largest disk is on the bottom.

The game is to move the stack of disks from the first post to the third post under the following constraints:

This can be accomplished recursively: to move K disks from post A to post C, first move K-1 disks to the remaining post, B, then move the one remaining disk from post A to post C. Moving the K-1 disks from post B to C is a reduced version of the original problem where the posts have been relabeled.

Legend has it that the Order of the Andes-Chilean Monks, also known as the Order of the ACM, have started the work of moving a 60-disk tower. When they finish, the world will end. Using the above recursive algorithm, this will take 1,152,921,504,606,846,975 moves.

You are to determine, to within a year, when the world will end.

INPUT: prob0.dat