这个模数比较有趣
可以求出 $\sqrt{5}$
然后就可以做了
$f_n=\dfrac{\sqrt{5}}{5}[(\dfrac{\sqrt{5}+1}{2})^n-(\dfrac{1-\sqrt{5}}{2})^n]$
分正负号考虑
令 $A=\dfrac{\sqrt{5}+1}{2},B=\dfrac{\sqrt{5}-1}{2}$
那么 $AB=1$
要解 $A^n+\dfrac{1}{A^n}=C$
令 $x=A^n$
那么 $x+\dfrac{1}{x}=C$
$x=\dfrac{c\pm \sqrt{c^2-4}}{2}$
再解一下 $n$
还有 Claris 提出的方法
$f_{n-1} f_{n+1} - f_n^2 = (-1)^n$
就可以求出 $f_{n+1}$ 从而通过矩阵的bsgs来求 $n$
以下代码是我的做法的，Claris的做法先坑着
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a),i##_end=(b);i<=i##_end;++i)
#define For(i,a,b) for(int i=(a),i##_end=(b);i<i##_end;++i)
#define per(i,a,b) for(int i=(b),i##_st=(a);i>=i##_st;--i)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define dbg(x) cerr<<#x" = "<<x<<endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Es(x,i) for(Edge*i=G[x];i;i=i->nxt)
typedef long long ll;
typedef pair<int,int> pii;
const int inf=~0u>>1,MOD=1e9+9;
inline int rd() {
int x,c,f=1;while(!isdigit(c=getchar()))f=c!='-';x=c-'0';
while(isdigit(c=getchar()))x=x*10+c-'0';return f?x:-x;
}
inline int pw(int n,int m){int r=1;for(;m;m>>=1,n=(ll)n*n%MOD)if(m&1)r=(ll)r*n%MOD;return r;}
/*
sqrt(5)=
383008016
616991993
*/
#define Inv(i) pw((i),MOD-2)
const int t5=616991993,i5=Inv(5),i2=Inv(2),it5=Inv(t5),g=13;
const int A=(t5+1)/2,B=(t5-1)/2;
int C;
int bsgs(int G,int Q){
static const int S=ceil(sqrt(MOD)+1);
map<int,int> F;
int t=Q;F[Q]=0;
rep(i,1,S){
t=(ll)t*G%MOD;
if(!F.count(t))F[t]=i;
}
t=pw(G,S);int q=1;
rep(i,1,S){
q=(ll)q*t%MOD;
if(F.count(q)){
return i*S-F[q];
}
}
return -1;
}
int F(int Q){
int t=pw(Q,MOD>>1);
if(t==-1)return -1;
else if(!t){
return 0;
}else{
t=bsgs(g,Q);
if(t==-1)return -1;
return pw(g,t/2);
}
}
inline int Calc(int t){
int q=1ll*t5*i5%MOD;
int p=(pw(A,t)+(t%2?1:-1)*pw(B,t))%MOD;
if(p<0)p+=MOD;p=(ll)p*q%MOD;
return p;
}
int ans=inf,AA;
inline void Upd(int C){
C%=MOD-1;
if(C<0)C+=MOD-1;
if(Calc(C)==AA)ans=min(ans,C);
}
int main(){
AA=C=rd();
C=(ll)C*t5%MOD;
{
int Q=((ll)C*C-4)%MOD;
if(Q<0)Q+=MOD;
int R=F(Q);
if(~R){
int a=(ll)(C+(R))%MOD*i2%MOD;
if(a<0)a+=MOD;
int b=bsgs(A,a);
if(~b)Upd(b);
a=(ll)(C-(R))%MOD*i2%MOD;
if(a<0)a+=MOD;
b=bsgs(A,a);
if(~b)Upd(b);
}
}
nxt:
{
int Q=((ll)C*C+4)%MOD;
if(Q<0)Q+=MOD;
int R=F(Q);
if(~R){
int a=(ll)(C+(R))%MOD*i2%MOD;
if(a<0)a+=MOD;
int b=bsgs(A,a);
if(~b)Upd(b);
a=(ll)(C-(R))%MOD*i2%MOD;
if(a<0)a+=MOD;
b=bsgs(A,a);
if(~b)Upd(b);
}
}
nxt2:
if(ans!=inf)cout<<ans<<endl;
else cout<<-1<<endl;
//cerr<<clock()<<endl;
}