题目描述 Description
在“1250 Fibonacci数列”中，我们求出了第n个Fibonacci数列的值。但是1250中，n<=109。现在，你的任务仍然是求出第n个Fibonacci数列的值，但是注意：n为整数，且1 <= n <= 100000000000000
输入描述 Input Description
输入有多组数据，每组数据占一行，为一个整数n(1 <= n <= 100000000000000)
输出描述 Output Description
输出若干行。每行输出第（对应的输入的）n个Fibonacci数（考虑到数会很大，mod 1000000007）
样例输入 Sample Input
3
4
5
样例输出 Sample Output
2
3
5
数据范围及提示 Data Size & Hint
1 <= n <= 100000000000000
数据虽然大了，但是矩阵快速幂仍然可以解决，而且速度飞快，只要注意防止longlong 相乘溢出即可
#define N 3
#define ll long long
#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
struct Jz{
int cal,line;
long long jz[N][N];
};
long long q=;
int read()
{
char s;
int ans=,ff=;
s=getchar();
while(s<''||s>'')
{
if(s=='-') ff=-;
s=getchar();
}
while(''<=s&&s<='')
{
ans=ans*+s-'';
s=getchar();
}
return ans*ff;
}
long long quick_mod(ll a,ll b)/*慢乘法防止溢出*/
{
a%=q;b%=q;
ll ans=;
while(b)
{
if(b&)
{
ans+=a;
ans%=q;//
}
b>>=;
a<<=;
a%=q;
}
return ans;
}
Jz martax(Jz x,Jz y)
{
Jz ans;
ans.line=x.line;
ans.cal=y.cal;
for(int i=;i<=ans.line;++i)
for(int j=;j<=ans.cal;++j)
{
ans.jz[i][j]=;
for(int k=;k<=x.cal;++k)
ans.jz[i][j]=(ans.jz[i][j]+quick_mod(x.jz[i][k],y.jz[k][j]))%q;
}
return ans;
}
long long Fast_martax(long long n)
{
if(n==||n==) return ;
n-=;
Jz ans,a;
a.cal=a.line=;
a.jz[][]=;a.jz[][]=;
a.jz[][]=;a.jz[][]=;
ans.line=;ans.cal=;
ans.jz[][]=;ans.jz[][]=;
while(n)
{
if(n&)
{
ans=martax(a,ans);
}
n>>=;
a=martax(a,a);
}
return ans.jz[][]%q;
}
int main()
{
long long n;
while(scanf("%lld",&n)==)
{
printf("%lld\n",Fast_martax(n));
}
return ;
}