珂朵莉在对抗第九兽的时候，渐渐开始出现“人格崩坏”的状况。

一般说来，崩坏会出现前世的记忆。

她的前世给她展示的画面是：

有一群一共 n 个妖精和兽排成一队，其中这一队列可以全是妖精或者全是兽，当然也可以是妖精和兽并存。

排队时还规定：兽不能落单（落单了就要被妖精砍死了），再明确一些，就是要么这个队列里面没有兽，如果有兽的话，必须 至少 两个兽肩并肩排在一起。

请问有多少种排法呢？由于数可能很大，请你对这个结果对 1e9 + 7 取模。

多组输入，请处理到文件结束。

数据组数不超过 20000。

一行一个数，代表 (n <= 10^10)。

输出方案数，对 1e9 + 7 取模。

假设妖精为 G，兽为 B。

n = 1 的情况： G
n = 2 的情况： BB GG
n = 3 的情况： BBG GGG GBB BBB

注意 n = 1 中没有 B 这种情况，因为这样算落单。