主页 讨论版 问题 名次 状态 统计
欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~
问题 A: 敬老师的手环

问题 A: 敬老师的手环

时间限制: 2 Sec  内存限制: 128 MB
提交: 5  解决: 4
[提交][状态][讨论版]

题目描述

敬老师是一位很喜欢手环的老师。快要七夕了,敬老师突发奇想,想要DIY一个手环然后送给Godv。现在敬老师拥有的材料是一堆1*2的小矩形,每个小矩形都是一样的,他想要用这些小矩形拼出一个宽度为2周长为n的手环(手环靠近手的一侧和远离手的一侧是不同的)。于是他想要知道自己能拼出多少种不同的手环。
但是敬老师是一位很敬业的老师,他忙于给萌新们备课,没时间算这个,于是就把问题丢给了无所事事的wy。现在,你能帮wy解决这个问题吗?

输入

多组数据,数据组数不超过1000,请处理到文件结束。每组数据占一行,包含一个数n(1<=n<=1e9)。

输出

每组数据输出一个数,即不相同的手环的种类数,要求答案对1e9+7取模后输出。

样例输入

1
2
3
4

样例输出

1
3
2
4

提示

当n=2时,如下的四种方案是将手环展开后可能看到的结果。前三种方案是两两不同的,第四种方案与第三种方案是等价的


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