#P2012. 拯救世界2

拯救世界2

题目背景

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

题目描述

经过 12 年的韬光养晦,世界末日再次来临(众人:什么鬼逻辑......)。

这次,小a 和 uim 已经做好了一切准备,顺利召唤出了 kkksc03 大神和 lzn 大神。然而,kkksc03 和 lzn 告诉他们,这次世界末日太过强大,他们已无法挽回,只有创世神 JOHNKRAM 能拯救这个世界。

然而,创世神 JOHNKRAM 是无法召唤的,除非把整个宇宙按照 E=mc2E=mc^2 全部转化成能量。因为根据 C_SUNSHINE 大神随手推算出的召唤定律,至少需要被召唤者百万亿分之一的能量才能召唤(众人:什么鬼定律......)。


当然,还有一种方法,那就是找出创世神 JOHNKRAM 的基因序列。普通人基因序列由 A、C、G、T 构成,创世神 JOHNKRAM 不是普通人(是个胖纸),基因序列也不一样。除了这四种普通的,还有乾、兑、离、震、巽、坎、艮、坤八种特殊基因。其中乾、坎、艮、震属阳,只能出现奇数次;坤、兑、离、巽属阴,只能出现偶数次。

现在只知道创世神 JOHNKRAM 的基因序列共有 nn 位,其他一概不知。小a 和 uim 想知道他们最多要试多少次,才能召唤出创世神 JOHNKRAM 。这个数字有可能很大,所以输出答案模 10910^9 即可(C_SUNSHINE 的忠告:远离八卦,远离肥胖)。

输入格式

输入由多组数据组成,每组数据一行,输入一个数 nn,输入以 00 结束。

输出格式

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

3
10
20
6
0
0
225116160
53238784
7680

提示

【数据范围】
对于 10%10\% 的数据:1n<251\le n < 25,数据不超过 1010 组;
对于 50%50\% 的数据:1n<2311\le n < 2^{31},数据不超过 10310^3 组;
对于 100%100\% 的数据:1n<2631\le n < 2^{63},数据不超过 2×1052\times 10^5 组。

【样例解释】
第一个数据解释:
只有 33 位,没有合法方案,故答案为 00

【备注】

附件:聊天记录(纯粹扯淡)

JOHNKRAM 8:50:33

喂喂,坑神之赛2可以开始了吧

C_SUNSHINE 8:50:34

[自动回复]恩!

JOHNKRAM 8:51:12

我准备把最后一题数据从 5050 放到 2632^{63}

C_SUNSHINE 8:51:12

[自动回复]恩!

JOHNKRAM 8:51:45

你同意喽?

C_SUNSHINE 8:51:46

[自动回复]恩!

C_SUNSHINE 11:58:50

你疯了吗?!

JOHNKRAM 11:58:52

[自动回复]您好,我现在有事不在,一会再和您联系。 不再提醒