Dragon's Party Gold Weighing

Byteasar the dragon is planning a magnificent party and wishes to present each guest with exactly n grammes of gold. To achieve this, he uses a beam balance and a collection of standard masses, where each mass weighs a power of four, i.e. \(4^k\) for nonnegative integers \(k\). He can use as many masses of any type as he wishes. In every weighing, the gold is placed on the left pan while masses may be placed on one or both pans. This gives rise to an equation of the form:

[ n + L = R, \quad\text{or equivalently}\quad n = R - L, ]

where \(R\) and \(L\) denote the total weight (sum of some \(4^k\) masses) on the right and left pans respectively. Equivalently, one must represent \(n\) in the form

[ n = \sum_{k\ge0} a_k 4^k, \quad a_k \in \mathbb{Z}, ]

with the cost of the representation defined as \(\sum_{k\ge0} |a_k|\) (each mass used—regardless of which pan it is on—incurs a cost of 1). Byteasar always chooses a representation that minimizes the total number of masses used. Moreover, to entertain his guests, he wishes to have a unique weighing method for each guest, that is, each representation must differ in its pattern of masses (either in the digits \(a_k\) or in their distribution over the pans).

Your task is to write a program that, given a number \(n\) (in grammes), finds the number of ways to represent \(n\) in the form above with minimum cost, and then outputs that number modulo \(10^9\). Note that negative coefficients correspond to placing masses on the left pan (with the gold) and positive coefficients correspond to placing masses on the right pan.

The allowed coefficients in an optimal representation turn out to lie in \(\{-2, -1, 0, 1, 2\}\), ensuring that each step of the representation (essentially a digit in a base-4 system) reduces the problem size by a factor of 4.

Input Example: If the input is 10, one optimal representation is
\(10=2\times4^0+1\times4^1\) with a cost of \(|2|+|1|=3\) or another method might yield a different cost. The program must choose the representation with the minimum cost and count the number of such representations, outputting the result modulo \(10^9\).

inputFormat

The input consists of a single integer \(n\), representing the number of grammes of gold each guest will receive.

\(n\) may be zero or positive. It is given on a single line.

outputFormat

Output a single integer --- the number of ways to represent \(n\) using the minimum number of masses, taken modulo \(10^9\).

sample

1

1