斐波那契数列：f[0]=0,f[1]=1,f[i]=f[i-1]+f[i-2](i>1)

求f[1]*f[1]+f[2]*f[2]+...+f[n]*f[n]的值

仅一行，一个正整数n

仅一行一个数，即所求的值，由于结果可能很大，需对1,000,000,007取模

3

6

对于100‰的数据，n<=1,000,000=10^6

然而：

对于200‰的数据，n<=9,000,000,000,000,000,000=9*10^18

对于500‰的数据，n<=10^500

对于1000‰的数据，n<=10^50000

引理1：

　　平方求和

#include<cstdio>using namespace std;typedef long long ll;ll n;const ll mod=1000000007;char s[50000];struct matrix{ll s[2][2];}A,F;ll mul(ll a,ll b){    ll res=0;    for(;b;b>>=1,a=(a+a)%mod) if(b&1) res=(res+a)%mod;    return res;}matrix operator *(const matrix &a,const matrix &b){    matrix c;    for(int i=0;i<2;i++){        for(int j=0;j<2;j++){            c.s[i][j]=0;            for(int k=0;k<2;k++){                c.s[i][j]+=mul(a.s[i][k],b.s[k][j]);                c.s[i][j]%=mod;            }        }    }    return c;}matrix fpow(matrix a,ll p){    matrix ans;    for(int i=0;i<2;i++) for(int j=0;j<2;j++) ans.s[i][j]=(i==j);    for(;p;p>>=1,a=a*a) if(p&1) ans=ans*a;    return ans;}void deal(){    for(int i=0;s[i];i++){        n=(n*10+s[i]-‘0‘)%(mod+1);    }}int main(){    scanf("%s",s);deal();    A.s[0][0]=A.s[0][1]=A.s[1][0]=1;A.s[1][1]=0;    F.s[0][0]=1;F.s[0][1]=F.s[1][0]=F.s[1][1]=0;    F=fpow(A,n)*F;    ll ans=F.s[0][0]*F.s[1][0]%mod;    printf("%lld\n",ans);    return 0;}