Code
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
ll n;
const int mod = 1000000007;
struct Matrix{
int r,c;
ll data[10][10];
Matrix(){
memset(data,0,sizeof(data));
}
Matrix(int r,int c){
this->r = r;
this->c = c;
memset(data,0,sizeof(data));
}
ll* operator [] (int pos){
return data[pos];
}
Matrix operator * (Matrix B){
Matrix C(r,B.c);
for(int i = 1;i <= r;i++){
for(int j = 1;j <= B.c;j++){
for(int k = 1;k <= c;k++){
C[i][j] = (C[i][j]%mod + (data[i][k]%mod)*(B[k][j]%mod)%mod)%mod;
}
}
}
return C;
}
};
Matrix Pow(Matrix A,ll b){
Matrix ret(A.r,A.c);
for(int i = 1;i <= A.r;i++) ret[i][i] = 1;//unit matrix <==> 1 (integer)
while(b){
if(b&1) ret = ret*A;
A = A*A;
b >>= 1;
}
return ret;
}
void solve(){
if(n <= 2){
printf("1
");
return;
}
Matrix P(2,2);
P[1][1] = P[1][2] = P[2][1] = 1;
P[2][2] = 0;
P = Pow(P,n - 2);
printf("%lld
",(P[1][1]%mod + P[1][2]%mod)%mod);
return;
}
int main(){
scanf("%lld",&n);
solve();
return 0;
}