#include <vector>
#include <iostream>
#include <fstream>
using namespace std;

typedef long long int64;

int64 MODULO = 666013;

vector<int64> multiplyMatrix(vector<int64> a, vector<int64> b) {
    vector<int64> r;
    r.push_back( (a[0] * b[0] + a[1]*b[2]) % MODULO);
    r.push_back( (a[0] * b[1] + a[1]*b[3]) % MODULO);
    r.push_back( (a[2] * b[0] + a[3]*b[2]) % MODULO);
    r.push_back( (a[2] * b[1] + a[3]*b[3]) % MODULO);
    return r;
}

vector<int64> powMatrix(vector<int64> a, int64 n) {
    if (n == 1) {
        return a;
    }
    if (n % 2 == 0) {
        vector<int64> r = powMatrix(a, n/2);
        return  multiplyMatrix(r, r);
    }
    return  multiplyMatrix(a, powMatrix(a, n-1));
}

main() {
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    int64 k;
    cin>>k;
    if (k<3) {
        cout<<1;
    } else {
        vector<int64> v;
        v.push_back(0);
        v.push_back(1);
        v.push_back(1);
        v.push_back(1);
        v = powMatrix(v, k-2);
        //cout<<v[0]<<" "<<v[1]<<"\n";
        //cout<<v[2]<<" "<<v[3]<<"\n";
        cout<<(v[1]+v[3])%MODULO;
    }


}