Byteasar the dragon intends to throw a party, to which he would like to invite many guests. Byteasar would also like to present each guest with an amount of gold to honour the party. Each should receive the same amount, so that no one's pride is hurt. The dragon is going to weigh out gold for subsequent guests with a beam balance. He has different types of standard masses at his disposal, each type weighing a certain power of four. Conveniently, Byteasar has lots of the standard masses, hence he may use any number of masses of any type (power of four) he finds appropriate. Byteasar will always lay the gold on the left weighing basin and the masses on the right or both weighing basins. The dragon wishes to use the least number of masses possible for each weighing. Furthermore, to entertain his guests, Byteasar would like to measure out the gold in unique manner for each person (ie. using different masses or distributing them among the weighing basins in a different way).
Since dragons' lack of arithmetic skills is legendary, Byteasar has aksed you to write a programme that will determine how many guests he may invite, that is, finds the maximum number of ways in which n grammes of gold can be weighed out using the minimum number of masses possible. Should you fare well, you will also get your share!
Write a programme that:
In the first and only line of the standard input there is one positive integer n (1 ≤ n < 101000). It is the amount of gold (in grammes) which Byteasar intends to present each guest with.
One integer should be written out to the standard output - the remainder of dividing by 109 the maximum number of guests Byteasar can invite (that is, the maximum number of ways in which n grammes of gold can be weighed out using the minimum number of masses possible).
7 masses are necessary to weigh out 166 grammes. Weighing out can be carried out in the following ways: