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

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

时间限制:1000 ms 内存限制:128 MB
提交:717 解决:78
[ 提交][ 状态][ 讨论版]

题目描述

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

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

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

有一群一共 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 这种情况，因为这样算落单。

来源

Chtholly_Mercury_Next_Door

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