问题 1281. -- 珂朵莉、威廉与第九兽

1281: 珂朵莉、威廉与第九兽

时间限制: 1 Sec  内存限制: 128 MB
提交: 705  解决: 73
[提交][状态][讨论版]

题目描述

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

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

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

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

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

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

输入

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

数据组数不超过 20000。

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

输出

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

样例输入

1
2
3

样例输出

1
2
4

提示

假设妖精为 G,兽为 B。



n = 1 的情况: G

n = 2 的情况: BB GG

n = 3 的情况: BBG GGG GBB BBB



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

来源

[提交][状态][讨论版]