// g++ -std=c++17 -DLOCAL a.cpp -o ex && ./ex >tst.out 2>&1
#include <bits/stdc++.h>

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
 
string to_string(const string& s) {
    return '"' + s + '"';
}
 
string to_string(const char* s) {
    return to_string((string) s);
}
 
string to_string(bool b) {
    return (b ? "true" : "false");
}
 
string to_string(vector<bool> v) {
    bool first = true;
    string res = "{";
    for (int i = 0; i < static_cast<int>(v.size()); i++) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(v[i]);
    }
    res += "}";
    return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
    string res = "";
    for (size_t i = 0; i < N; i++) {
        res += static_cast<char>('0' + v[i]);
    }
    return res;
}
 
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
 
void debug_out() { cerr << "   "; }
void debug_out_nl() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

template <typename Head, typename... Tail>
void debug_out_nl(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out_nl(T...);
}
 
#ifdef LOCAL
#define dbg(...) cerr << "#" << #__VA_ARGS__ << ":", debug_out(__VA_ARGS__)
#define nl(...) cerr << "#" << #__VA_ARGS__ << ":", debug_out_nl(__VA_ARGS__)
#else
#define dbg(...) 69
#define nl(...) 42
#endif

#define ll long long
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random(ll st, ll dr) {
    assert(st <= dr);
    return st + rng() % (dr - st + 1);
}

const int MOD = 1e9 + 7;
const int N = 2e5 + 10;

namespace Modular {
    template<int MOD>
    struct ModInt {
        long long v;
        ModInt(long long _v = 0) {v = (-MOD < _v && _v < MOD) ? _v : _v % MOD; if (v < 0) v += MOD;}
        ModInt& operator += (const ModInt &other) {v += other.v; if (v >= MOD) v -= MOD; return *this;}
        ModInt& operator -= (const ModInt &other) {v -= other.v; if (v < 0) v += MOD; return *this;}
        ModInt& operator *= (const ModInt &other) {v = v * other.v % MOD; return *this;}
        ModInt& operator /= (const ModInt &other) {return *this *= inverse(other);}
        bool operator == (const ModInt &other) const {return v == other.v;}
        bool operator != (const ModInt &other) const {return v != other.v;}
        friend ModInt operator + (ModInt a, const ModInt &b) {return a += b;}
        friend ModInt operator - (ModInt a, const ModInt &b) {return a -= b;}
        friend ModInt operator * (ModInt a, const ModInt &b) {return a *= b;}
        friend ModInt operator / (ModInt a, const ModInt &b) {return a /= b;}
        friend ModInt operator - (const ModInt &a) {return 0 - a;}
        friend ModInt power(ModInt a, long long b) {ModInt ret(1); while (b > 0) {if (b & 1) ret *= a; a *= a; b >>= 1;} return ret;}
        friend ModInt inverse(ModInt a) {return power(a, MOD - 2);}
        friend ostream& operator << (ostream &os, const ModInt &m) {return os << m.v;}
    };
    
    const int N = 2e5 + 5; // CHANGE !!!
    const int MOD = 666013; // CHANGE !!!
    typedef ModInt<MOD> Mint;

    Mint power(long long _a, long long b) {Mint ret(1), a(_a); while (b > 0) {if (b & 1) ret *= a; a *= a; b >>= 1;} return ret;}

    Mint fact[N], inv[N];
    void init() {
        fact[0] = 1;
        for (int i = 1; i < N; i++)
            fact[i] = fact[i - 1] * i;
        inv[N - 1] = inverse(fact[N - 1]);
        for (int i = N - 2; i >= 0; i--)
            inv[i] = inv[i + 1] * (i + 1);
    }

    Mint choose(int n, int k) {
        return ((n < k || k < 0) ? 0 : fact[n] * inv[k] * inv[n - k]);
    }
}

using Modular::Mint;

template<typename T>
struct MatrixExpo {
    int N;
    int M;
    vector<vector<T> > data;

    MatrixExpo(int _N, int _M, bool init = false) : N(_N), M(_M), data(N, vector<T>(M, 0)) {
        if (init) {
            // init matrix here
            data[0][1] = 1;
            data[1][0] = 1;
            data[1][1] = 1;
        }
    }

    void identity() {
        assert(N == M);

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                data[i][j] = i == j;
            }
        }
    }

    MatrixExpo& operator *= (const MatrixExpo &other) {
        assert(M == other.N);

        vector<vector<T> > aux(N, vector<T>(other.M, 0));

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < other.M; j++) {
                for (int k = 0; k < M; k++) {
                    aux[i][j] += data[i][k] * other.data[k][j];
                }
            }
        }

        M = other.M;
        data = aux;

        return *this;
    }
        
    friend MatrixExpo operator * (MatrixExpo a, const MatrixExpo &b) {
        return a *= b;
    }

    friend MatrixExpo power(MatrixExpo a, long long b) {
        MatrixExpo ret(a.N, a.M); 
        ret.identity();
        while (b > 0) {
            if (b & 1) 
                ret *= a; 
            a *= a; 
            b >>= 1;
        } 
        
        return ret;
    }
};

struct Rec {
    Mint kth(long long k) {
        MatrixExpo<Mint> f(1, 2, false);
        f.data[0][0] = 0;
        f.data[0][1] = 1;

        if (k < 2) {
            return f.data[0][k];
        }

        MatrixExpo<Mint> mat(2, 2, true);
        f *= power(mat, k - 1);

        return f.data[0][1];
    }
};

void solve(int test, istream &cin, ostream &cout) {
    int k;
    cin >> k;

    Rec rec;
    cout << rec.kth(k);

    // cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}

int main() {
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    bool multiTest = false;

    int t;    
    if (multiTest) {
        cin >> t;
    } else {
        t = 1;
    }

    for (int test = 1; test <= t; test++) {
        solve(test, cin, cout);
    }

    return 0;
}