#OJ1557. g

g

g

Time Limit: 2 Sec  Memory Limit: 256 MB

Description

  考虑一种字符串,它只由字符'a'和字符'b'组成,现在给你一个字符串长度L,则这种字符串一共有2^L种(2^L代表2的L次方),问在这2^L种字符串中,有多少个字符串既不含有子串"aba",又不含有子串"aaa"。   结果可能非常大,请输出 结果mod1000000007(mod是取余运算)。

Input

  输入有多行,每行一个数字L(1<=L<=10^18),代表字符串的长度。

Output

  对于每行输入,输出结果mod1000000007

Sample Input

2
5

Sample Output

4
15

HINT

Append Code