题目描述

斐波那契数列是指这样的数列：数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。

给出一个正整数k，要求菲波那契数列中第k个数是多少。

结果可能很大，请输出对 1e9+7 取模后的结果。

输入格式

输入一行，包含一个正整数k（1≤k≤100000）。

输出格式

输出一行，包含一个正整数，表示菲波那契数列中第 k 个数的大小。

样例输入

19

样例输出

4181

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 1E5;
const int MOD = 1E9+7;
int f[N+1];
int main()
{
	int n;
	cin>>n;
	f[1] = f[2] = 1;
	for(int i=3;i<=n;i++)
	{
		f[i] = (f[i-1] + f[i-2]) % MOD;
	}
	cout<<f[n];
	return 0;
}