无聊的UMR

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

3776

UMR 闲来无聊玩起了自己的名字,现在的她想知道对于给定的长度 n,只用自己的 ‘U’, ‘M’, ‘R’ 这 3 个字符最多能构成多少种不同的字符串。但是因为 UMR 并不喜欢 MM ,所以 MM 是不能连在一起的。

Input

输入数据有多组(数据组数不超过 100000),到 EOF 结束。

每组输入一个整数 n (1 <= n <= 100000),表示 UMR 想要构成的字符串长度。

Output

对于每组数据,输出一个整数,表示 UMR 只用 ‘U’, ‘M’, ‘R’ 这 3 个字符并且 MM 不能连在一起的最多能构成多少种不同的长度为 n 的字符串的个数(因为结果可能很大,请输出对 1000000007 取模之后的结果)。

Sample Input

1
2
233

Sample Output

3
8
546261695

Hint

Source

【2017年寒假集训 结训赛1】UMR