Monkey Tower

Monkey Tower follows the same rules as the Tower of Hanoi, except that it has 4 pegs.

Initially, N disks of distinct sizes are stacked on peg 1. The goal is to move all disks to peg 4.

Each move must follow these rules.

1. A larger disk may not be placed on top of a smaller disk.
2. Exactly one disk may be moved to another peg at a time.

Find the minimum number of moves needed to move all N disks from the initial state to peg 4.

The first line contains the number of disks N. N is a positive integer not greater than 1,000,000.

Print the minimum number of moves needed to move the N disks, modulo 9901.

This problem can be solved using the Frame-Stewart conjecture for the optimal number of moves in the four-peg Tower of Hanoi.