拯救世界2

前三题太弱了嘛，在看看最后一道渣题。

经过 12 年的韬光养晦，世界末日再次来临（众人：什么鬼逻辑......）。 这次，小a 和 uim 已经做好了一切准备，顺利召唤出了 kkksc03 大神和 lzn 大神。然而，kkksc03 和 lzn 告诉他们，这次世界末日太过强大，他们已无法挽回，只有创世神 JOHNKRAM 能拯救这个世界。 然而，创世神 JOHNKRAM 是无法召唤的，除非把整个宇宙按照 $E=mc^2$ 全部转化成能量。因为根据 C\_SUNSHINE 大神随手推算出的召唤定律，至少需要被召唤者百万亿分之一的能量才能召唤（众人：什么鬼定律......）。 **** 当然，还有一种方法，那就是找出创世神 JOHNKRAM 的基因序列。普通人基因序列由 A、C、G、T 构成，创世神 JOHNKRAM 不是普通人（是个胖纸），基因序列也不一样。除了这四种普通的，还有乾、兑、离、震、巽、坎、艮、坤八种特殊基因。其中乾、坎、艮、震属阳，只能出现奇数次；坤、兑、离、巽属阴，只能出现偶数次。 现在只知道创世神 JOHNKRAM 的基因序列共有 $n$ 位，其他一概不知。小a 和 uim 想知道他们最多要试多少次，才能召唤出创世神 JOHNKRAM 。这个数字有可能很大，所以输出答案模 $10^9$ 即可（C\_SUNSHINE 的忠告：远离八卦，远离肥胖）。

输入由多组数据组成，每组数据一行，输入一个数 $n$，输入以 $0$ 结束。

对于每组数据，输出一行一个整数，表示答案对 $10^9$ 取模的结果。

3
10
20
6
0

0
225116160
53238784
7680

【数据范围】 对于 $10\%$ 的数据：$1\le n < 25$，数据不超过 $10$ 组； 对于 $50\%$ 的数据：$1\le n < 2^{31}$，数据不超过 $10^3$ 组； 对于 $100\%$ 的数据：$1\le n < 2^{63}$，数据不超过 $2\times 10^5$ 组。 【样例解释】 第一个数据解释： 只有 $3$ 位，没有合法方案，故答案为 $0$。 【备注】 附件：聊天记录（纯粹扯淡） JOHNKRAM 8:50:33 喂喂，坑神之赛2可以开始了吧 C_SUNSHINE 8:50:34 [自动回复]恩！ JOHNKRAM 8:51:12 我准备把最后一题数据从 $50$ 放到 $2^{63}$。 C_SUNSHINE 8:51:12 [自动回复]恩！ JOHNKRAM 8:51:45 你同意喽？ C_SUNSHINE 8:51:46 [自动回复]恩！ C_SUNSHINE 11:58:50 你疯了吗？！ JOHNKRAM 11:58:52 [自动回复]您好，我现在有事不在，一会再和您联系。 不再提醒