提供一个可以处理无理数的黑科技。

定义新的虚数单位 $i,i=\sqrt{5}.$

对于 $fib$ 数列的通项公式：

$$F_n = \dfrac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right]$$

将 $\sqrt{5}$ 视作虚数单位。原式可化为：

$$F_n = \dfrac{1}{i}\left[\left(\dfrac{1+i}{2}\right)^n-\left(\dfrac{1-i}{2}\right)^n\right]$$

需要注意： $i^2 = \sqrt{5}^2 = 5.$

$zz'=(a+bi)(c+di)=ac+(ad+bc)i+bdi^2=ac+5bd+(ad+bc)i$

答案是其实数部分。

#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
ll p=1e9+7;
struct cplx{
    ll a,b;
    cplx(ll A=0,ll B=0): a(A), b(B) {}
    cplx operator +(const cplx& tt)const{
        ll u=a+tt.a,v=b+tt.b;
        return cplx(u%p,v%p);
    }
    cplx operator -(const cplx& tt)const{
        ll u=a-tt.a+p,v=b-tt.b+p;
        return cplx(u%p,v%p);
    }
    cplx operator *(const cplx& tt)const{
        ll u=a*tt.a+5*b*tt.b,v=a*tt.b+b*tt.a;
        return cplx(u%p,v%p);
    }
}; 
ll qpow(int a,int b){
    ll base=a,res=1;
    while(b){
        if(b&1)  res=res*base%p;
        base=base*base%p, b>>=1;
    }
    return res;
}
cplx Qpow(cplx a,int b){
    cplx base=a,res=cplx(1,0);
    while(b){
        if(b&1)  res=res*base;
        base=base*base, b>>=1;
    }
    return res;
}
signed main(){
    ll n; cin>>n;
    ll inv2=qpow(2,p-2);
    cplx x=cplx(inv2,inv2);
    cplx y=cplx(inv2,p-inv2);
    cplx xx=Qpow(x,n),yy=Qpow(y,n);
    cplx res=xx-yy;
    ll ans=res.b;
    printf("%lld\n",ans%p);
}