测评记录，本地测是对的

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 150, mod = 1e9 + 7;

struct Matrix {
	int r, c, b[N][N];
	
	void cleas() {
		for (int i = 1; i <= r; i ++)
			for (int j = 1; j <= c; j ++)
				b[i][j] = 0;
		return ;
	}
	
	Matrix operator * (const Matrix& x) {
		
		Matrix res;
		
		res.cleas();
		
		res.r = r, res.c = x.c;
		
		for (int i = 1; i <= r; i ++) 
			for (int j = 1; j <= x.c; j ++) 
				for (int k = 1; k <= c; k ++)
					res.b[i][j] = (res.b[i][j] + b[i][k] * x.b[k][j] % mod) % mod;
		
		return res;
	}
	
} ans, base;

void Qpow(int t) {
	
	while (t) {
		if (t & 1) ans = ans * base;
		base = base * base, t >>= 1;
	}
	
}

int n;

signed main() {
	
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	cin >> n;
	
	if (n <= 2) {
		cout << "1";
		return 0;
	}
	
	base.b[1][1] = base.b[1][2] = base.b[2][1] = 1, base.b[2][2] = 0;
	ans.b[1][1] = ans.b[1][2] = 1;
	
	ans.r = base.r = base.c = ans.c = 2;
	
	Qpow(n - 2);
	
	cout << ans.b[1][1] % mod;
	
	return 0;
}