// 100 Puncte
#include <bits/stdc++.h>
#define ll long long

using namespace std;

ifstream fin ("kfib.in");
ofstream fout ("kfib.out");

// Fara long long peste tot da overflow, chiar si pentru ct asa mic
class mat {
private:
    const ll ct = 666013;
    ll a, b, c, d;
public:
    void setMatrix (int af, int bf, int cf, int df) {
        a = af; b = bf; c = cf; d = df;
    }
    void addMatrix (mat m1) {
        a+=m1.a; b+=m1.b; c+=m1.c; d+=m1.d;
        if (a>=ct) a%=ct;
        if (b>=ct) b%=ct;
        if (c>=ct) c%=ct;
        if (d>=ct) d%=ct;
    }
    void multiplyMatrix(mat m1) {
        ll na, nb, nc, nd;
        // Daca fac direct cu a, b, c, d se updateaza in timp real si se strica
        na = a*m1.a + b*m1.c;
        nb = a*m1.b + b*m1.d;
        nc = c*m1.a + d*m1.c;
        nd = c*m1.b + d*m1.d;
        a = na; b = nb; c = nc; d = nd;
        if (a>=ct) a%=ct;
        if (b>=ct) b%=ct;
        if (c>=ct) c%=ct;
        if (d>=ct) d%=ct;
    }
    int getFibo() {
        return c;
    }
    void display() {
        cout<<a<<' '<<b<<endl;
        cout<<c<<' '<<d<<endl;
        cout<<endl;
    }
};

int main()
{
    fin.tie(0); fin.sync_with_stdio(false);
    int b; fin>>b;
    mat result, fibo;
    result.setMatrix(1, 0, 0, 1);
    fibo.setMatrix(0, 1, 1, 1);
    while (b) {
        // fibo.display();
        // Neaparat in ordinea asta in while (descompunerea in baza 2)
        if (b%2==1) result.multiplyMatrix(fibo);
        fibo.multiplyMatrix(fibo);
        b/=2;
    }
    fout<<result.getFibo();
    return 0;
}