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

问题 E: Feibonaqi数列

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

题目描述

北雷老中医不懂 Fibonacci,于是他定义了一种名叫Feibonaqi的数列,数列满足以下要求:
1.f(0)=0,f(1)=1
2.f(n)=2f(n-1)+f(n-2),n>1
那么问题来了,这个数列的第n项是多少呢?
(不为难大家用高精度了,你只需要将结果对1,000,000,007取模后输出即可)

输入

多组数据
每组数据一行,包含一个整数n,1<n<1,000,000,000

输出

每组数据输出一个整数,即为f(n)对1,000,000,007取模后的结果

样例输入

2
3
4

样例输出

2
5
12

提示

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