#include <iostream>
using namespace std;
typedef long long ll;
 
const ll MOD = 1e9 + 7;
 
// Returns F(n)
ll fib(ll n) {
    ll a = 0, b = 1, c, d;
    for (ll i = 63 - __builtin_clzll(n); i >= 0; --i) {
        // Double the index
        c = (a * ((2 * b % MOD - a + MOD) % MOD)) % MOD;
        d = (a * a % MOD + b * b % MOD) % MOD;
        if ((n >> i) & 1) {
            a = d;
            b = (c + d) % MOD;
        } else {
            a = c;
            b = d;
        }
    }
    return a;
}
 
int main() {
    ll n;
    cin >> n;
    cout << fib(n) << endl;
    return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKCmNvbnN0IGxsIE1PRCA9IDFlOSArIDc7CgovLyBSZXR1cm5zIEYobikKbGwgZmliKGxsIG4pIHsKICAgIGxsIGEgPSAwLCBiID0gMSwgYywgZDsKICAgIGZvciAobGwgaSA9IDYzIC0gX19idWlsdGluX2NsemxsKG4pOyBpID49IDA7IC0taSkgewogICAgICAgIC8vIERvdWJsZSB0aGUgaW5kZXgKICAgICAgICBjID0gKGEgKiAoKDIgKiBiICUgTU9EIC0gYSArIE1PRCkgJSBNT0QpKSAlIE1PRDsKICAgICAgICBkID0gKGEgKiBhICUgTU9EICsgYiAqIGIgJSBNT0QpICUgTU9EOwogICAgICAgIGlmICgobiA+PiBpKSAmIDEpIHsKICAgICAgICAgICAgYSA9IGQ7CiAgICAgICAgICAgIGIgPSAoYyArIGQpICUgTU9EOwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIGEgPSBjOwogICAgICAgICAgICBiID0gZDsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gYTsKfQoKaW50IG1haW4oKSB7CiAgICBsbCBuOwogICAgY2luID4+IG47CiAgICBjb3V0IDw8IGZpYihuKSA8PCBlbmRsOwogICAgcmV0dXJuIDA7Cn0K

MTAwMDAwMDAw

100000000