PROBLEM STATEMENT

Marvin plays a simple game. The game is played with an infinite supply of marbles and five bags, 
labeled "bag 0" through "bag 4".



At the beginning, Marvin takes N marbles (where N is a nonnegative integer) and places them into 
bag 0. The remaining four bags are left empty.
Marvin then follows this simple algorithm:



    Add a marble into bag 1.
    Repeat forever:
        Add a marble into bag 1.
        Empty bag 4.
        While there are marbles in bag 0:
            While there are marbles both in bag 0 and in bag 1:
                Remove a marble from bag 0.
                Remove a marble from bag 1.
                Add a marble into bag 2.
                Add a marble into bag 3.
            End While
            Add a marble into bag 4.
            If bags 0 and 1 are both empty:
                Move all marbles from bag 3 to bag 4.
                TERMINATE THE GAME
            End If
            Move all marbles from bag 3 to bag 1.
        End While
        Move all marbles from bag 2 to bag 0.
    End Repeat



You are given a long long N. Count the number of times a marble enters a bag during Marvin's game. 
That is, compute X+Y, where X is the number of times a marble is added to some bag, and Y is the 
number of times a marble is moved from one bag to another. To avoid overflows, return just the 
value ((X+Y) modulo 1,000,000,009). If Marvin's game does not terminate for the given N, return -1 
instead.


DEFINITION
Class:MinskyMystery
Method:computeAnswer
Parameters:long long
Returns:int
Method signature:int computeAnswer(long long N)


NOTES
-Suppose there are M marbles in bag A. The instruction "Move all marbles from bag A to bag B." 
then counts as M individual moves.
-Note that N is allowed to be zero.


CONSTRAINTS
-N will be between 0 and 10^12, inclusive.


EXAMPLES

0)
2

Returns: 9



1)
3

Returns: 27



2)
4

Returns: 16



3)
2401

Returns: 59058



4)
24

Returns: 86

 This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.