拯救世界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。这个数字有可能很大,所以输出答案模1,000,000,000即可。(C\_SUNSHINE的忠告:远离八卦,远离肥胖)

输入输出格式

输入格式


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

输出格式


对于每组数据输出一行,每一行一个数,为答案模1,000,000,000的结果。

输入输出样例

输入样例 #1

3
10
20
6
0

输出样例 #1

0
225116160
53238784
7680

说明

【数据范围】 对于10%的数据:1≤N<25,数据不超过10组; 对于50%的数据:1≤N<2^31,数据不超过1,000组; 对于100%的数据:1≤N<2^63,数据不超过200,000组. 【限制】 时间限制:2s,内存限制:256M 【样例解释】 第一个数据解释: 只有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 [自动回复]您好,我现在有事不在,一会再和您联系。 不再提醒