Description

After 12 years of hiding their strength, the end of the world comes again (everyone: what kind of logic is that...).

This time, xiao a and uim have prepared everything and successfully summoned the gurus kkksc03 and lzn. However, kkksc03 and lzn told them that this doomsday is too powerful to reverse. Only the Creator God JOHNKRAM can save the world.

But the Creator God JOHNKRAM cannot be summoned, unless the entire universe is converted into energy according to $E=mc^2$. Based on the summoning law casually derived by the guru C_SUNSHINE, at least one quadrillionth of the summonee’s energy is required to summon them (everyone: what kind of law is that...).

Of course, there is another way: find the genetic sequence of the Creator God JOHNKRAM. A normal human gene sequence consists of A, C, G, T. The Creator God JOHNKRAM is not a normal person (he’s a chubby guy), so his genetic sequence is different. Besides these four ordinary ones, there are eight special genes: 乾 (Qian), 兑 (Dui), 离 (Li), 震 (Zhen), 巽 (Xun), 坎 (Kan), 艮 (Gen), 坤 (Kun). Among them, 乾, 坎, 艮, 震 are “yang” and can only appear an odd number of times; 坤, 兑, 离, 巽 are “yin” and can only appear an even number of times.

Now we only know that the Creator God JOHNKRAM’s genetic sequence has $n$ positions; nothing else is known. xiao a and uim want to know the maximum number of attempts they would need in order to summon the Creator God JOHNKRAM. This number can be large, so output the answer modulo $10^9$ (C_SUNSHINE’s advice: stay away from the Eight Trigrams, stay away from obesity).

Input Format

Multiple test cases. Each test case contains a single integer $n$ on one line. Input terminates with $0$.

Output Format

For each test case, output a single integer on one line: the answer modulo $10^9$.

3
10
20
6
0

0
225116160
53238784
7680

Hint

Constraints
For $10\%$ of the testdata: $1 \le n < 25$, the number of test cases does not exceed $10$.
For $50\%$ of the testdata: $1 \le n < 2^{31}$, the number of test cases does not exceed $10^3$.
For $100\%$ of the testdata: $1 \le n < 2^{63}$, the number of test cases does not exceed $2 \times 10^5$.

Sample Explanation
Explanation for the first sample:
There are only $3$ positions, so there is no valid configuration. The answer is $0$.

Notes

Attachment: chat log (pure nonsense)

JOHNKRAM 8:50:33
Hey hey, can the Pit God Contest 2 start now?

C_SUNSHINE 8:50:34
[Auto-reply] En!

JOHNKRAM 8:51:12
I’m planning to raise the last problem’s range from $50$ to $2^{63}$.

C_SUNSHINE 8:51:12
[Auto-reply] En!

JOHNKRAM 8:51:45
You agree?

C_SUNSHINE 8:51:46
[Auto-reply] En!

C_SUNSHINE 11:58:50
Are you crazy?!

JOHNKRAM 11:58:52
[Auto-reply] Hello, I’m busy right now and will get back to you later. Do not remind again.

Translated by ChatGPT 5