Time Limit: 3000 MS    Memory Limit: 65536 K 


Description

最近医学研究者发现了一种新病毒,因为其蔓延速度与最近Internet上传播的“红色代码” 不相上下,故被称为“红色病毒”。经研究发现,该病毒及其变种的DNA的一条单链中,胞嘧啶 ,腺嘧啶的个数之和为偶数。这虽然是一个重大发现,但还不是该病毒的最主要特征,因为这个 特征实在太弱了。为了搞清楚该病毒的特征,软件工程师Grant对此产生了兴趣。他想知道在 这个特征下,可能成为病毒的DNA序列的个数。 更确切地说,Grant需要统计所有满足下列条件的长度为n的字符串的个数: (1) 字符串仅有A,T,C,G四个英文字母组成。 (2) A和C的个数之和为偶数(可以为0)。 当n=2时,所有满足条件的字符串有如下六个:TT,TG,GT,GG,AA,CC,AC,CA。 由于这个数可能非常庞大,你只需要给出这个数字对1000000007取余后的结果。

Input

每行一个整数n( 1 <= n <= 109 ).

Output

输出一个整数。

Sample Input

2

Sample Output

8

Source

经典问题