Summoning the Creator Gene

After 12 years of quiet development, the apocalypse has returned. This time, although the legendary kkksc03 and lzn have been summoned, they declare that only the Creator God JOHNKRAM can save the world. However, summoning JOHNKRAM is not easy. One method requires converting the entire universe into energy according to the famous equation \(E=mc^2\), and even then a minuscule fraction is enough according to C_SUNSHINE's law. The other method is to try to guess the genetic sequence of JOHNKRAM.

The gene sequence of an ordinary human consists of four characters: A, C, G and T. But JOHNKRAM is no ordinary being – his gene sequence is of length \(n\) and is made up not only of the four ordinary genes but also of 8 special genes: 乾, 兑, 离, 震, 巽, 坎, 艮, 坤. Among these, the genes 乾, 坎, 艮, 震 are yang and must occur an odd number of times, while the genes 坤, 兑, 离, 巽 are yin and must occur an even number of times. There is no restriction on the usage of the four ordinary genes.

Your task is to compute, given the length \(n\) of JOHNKRAM's gene sequence, the maximum number of attempts one might need in order to try every possible valid gene sequence that meets these parity constraints. Since the answer can be very large, output it modulo \(10^9\). (A word of advice from C_SUNSHINE: Stay away from the mysterious trigrams and fat people!)

inputFormat

The input consists of a single integer \(n\) (\(1 \le n \le 10^{12}\) or as specified by the problem) which represents the length of the gene sequence.

Note that even though \(n\) might be very large, the answer is guaranteed to be an integer which we ask you to output modulo \(10^9\).

outputFormat

Output a single integer: the number of valid gene sequences modulo \(10^9\>.

sample

1

0