#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9+7;
using type = long long;
struct Matrix {
vector <vector <type> > data;
long long row() const { return data.size(); }
long long col() const { return data[0].size(); }
auto & operator [] (long long i) { return data[i]; }
const auto & operator[] (long long i) const { return data[i]; }
Matrix() = default;
Matrix(long long r, long long c): data(r, vector <type> (c)) { }
Matrix(const vector <vector <type> > &d): data(d) { }
friend ostream & operator << (ostream &out, const Matrix &d) {
for (auto x : d.data) {
for (auto y : x) out << y << ' ';
out << '\n';
}
return out;
}
static Matrix identity(long long n) {
Matrix a = Matrix(n, n);
while (n--) a[n][n] = 1;
return a;
}
Matrix operator * (const Matrix &b) {
Matrix a = *this;
assert(a.col() == b.row());
Matrix c(a.row(), b.col());
for (long long i = 0; i < a.row(); ++i)
for (long long j = 0; j < b.col(); ++j)
for (long long k = 0; k < a.col(); ++k){
c[i][j] += 1ll * a[i][k] % mod * (b[k][j] % mod) % mod;
c[i][j] %= mod;
}
return c;
}
Matrix pow(long long exp) {
assert(row() == col());
Matrix base = *this, ans = identity(row());
for (; exp > 0; exp >>= 1, base = base * base)
if (exp & 1) ans = ans * base;
return ans;
}
};
signed main(){
Matrix a({
{1, 1},
{1, 0}
});
long long n;
cin >> n;
Matrix tmp = a.pow(n - 2);
cout << (tmp[0][0] + tmp[0][1]) % mod << '\n';
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiAKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIApjb25zdCBsb25nIGxvbmcgbW9kID0gMWU5Kzc7CiAKdXNpbmcgdHlwZSA9IGxvbmcgbG9uZzsKIApzdHJ1Y3QgTWF0cml4IHsKICAgIHZlY3RvciA8dmVjdG9yIDx0eXBlPiA+IGRhdGE7CiAKICAgIGxvbmcgbG9uZyByb3coKSBjb25zdCB7IHJldHVybiBkYXRhLnNpemUoKTsgfQogCiAgICBsb25nIGxvbmcgY29sKCkgY29uc3QgeyByZXR1cm4gZGF0YVswXS5zaXplKCk7IH0KIAogICAgYXV0byAmIG9wZXJhdG9yIFtdIChsb25nIGxvbmcgaSkgeyByZXR1cm4gZGF0YVtpXTsgfQogCiAgICBjb25zdCBhdXRvICYgb3BlcmF0b3JbXSAobG9uZyBsb25nIGkpIGNvbnN0IHsgcmV0dXJuIGRhdGFbaV07IH0KIAogICAgTWF0cml4KCkgPSBkZWZhdWx0OwogCiAgICBNYXRyaXgobG9uZyBsb25nIHIsIGxvbmcgbG9uZyBjKTogZGF0YShyLCB2ZWN0b3IgPHR5cGU+IChjKSkgeyB9CiAKICAgIE1hdHJpeChjb25zdCB2ZWN0b3IgPHZlY3RvciA8dHlwZT4gPiAmZCk6IGRhdGEoZCkgeyB9CiAKICAgIGZyaWVuZCBvc3RyZWFtICYgb3BlcmF0b3IgPDwgKG9zdHJlYW0gJm91dCwgY29uc3QgTWF0cml4ICZkKSB7CiAgICAgICAgZm9yIChhdXRvIHggOiBkLmRhdGEpIHsKICAgICAgICAgICAgZm9yIChhdXRvIHkgOiB4KSBvdXQgPDwgeSA8PCAnICc7CiAgICAgICAgICAgIG91dCA8PCAnXG4nOwogICAgICAgIH0KICAgICAgICByZXR1cm4gb3V0OwogICAgfQogCiAgICBzdGF0aWMgTWF0cml4IGlkZW50aXR5KGxvbmcgbG9uZyBuKSB7CiAgICAgICAgTWF0cml4IGEgPSBNYXRyaXgobiwgbik7CiAgICAgICAgd2hpbGUgKG4tLSkgYVtuXVtuXSA9IDE7CiAgICAgICAgcmV0dXJuIGE7CiAgICB9CiAKICAgIE1hdHJpeCBvcGVyYXRvciAqIChjb25zdCBNYXRyaXggJmIpIHsKICAgICAgICBNYXRyaXggYSA9ICp0aGlzOwogICAgICAgIGFzc2VydChhLmNvbCgpID09IGIucm93KCkpOwogICAgICAgIE1hdHJpeCBjKGEucm93KCksIGIuY29sKCkpOwogICAgICAgIGZvciAobG9uZyBsb25nIGkgPSAwOyBpIDwgYS5yb3coKTsgKytpKQogICAgICAgICAgICBmb3IgKGxvbmcgbG9uZyBqID0gMDsgaiA8IGIuY29sKCk7ICsraikKICAgICAgICAgICAgICAgIGZvciAobG9uZyBsb25nIGsgPSAwOyBrIDwgYS5jb2woKTsgKytrKXsKICAgICAgICAgICAgICAgICAgICBjW2ldW2pdICs9IDFsbCAqIGFbaV1ba10gJSBtb2QgKiAoYltrXVtqXSAlIG1vZCkgJSBtb2Q7CiAgICAgICAgICAgICAgICAgICAgY1tpXVtqXSAlPSBtb2Q7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgcmV0dXJuIGM7CiAgICB9CiAKICAgIE1hdHJpeCBwb3cobG9uZyBsb25nIGV4cCkgewogICAgICAgIGFzc2VydChyb3coKSA9PSBjb2woKSk7CiAgICAgICAgTWF0cml4IGJhc2UgPSAqdGhpcywgYW5zID0gaWRlbnRpdHkocm93KCkpOwogICAgICAgIGZvciAoOyBleHAgPiAwOyBleHAgPj49IDEsIGJhc2UgPSBiYXNlICogYmFzZSkKICAgICAgICAgICAgaWYgKGV4cCAmIDEpIGFucyA9IGFucyAqIGJhc2U7CiAgICAgICAgcmV0dXJuIGFuczsKICAgIH0KfTsKIApzaWduZWQgbWFpbigpewogICAgTWF0cml4IGEoewogICAgICAgIHsxLCAxfSwKICAgICAgICB7MSwgMH0KICAgIH0pOwogCiAKICAgIGxvbmcgbG9uZyBuOwogICAgY2luID4+IG47CiAgICBNYXRyaXggdG1wID0gYS5wb3cobiAtIDIpOwogICAgY291dCA8PCAodG1wWzBdWzBdICsgdG1wWzBdWzFdKSAlIG1vZCA8PCAnXG4nOwp9Cg==