#include <iostream>
#include <bits/stdc++.h>
#define mod 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

long long n;

struct Mat{
    long long m[2][2];
};

Mat inmult(Mat a, Mat b) {
    Mat c;
    c.m[0][0] = (a.m[0][0]*b.m[0][0] + a.m[0][1]*b.m[1][0]) % mod;
    c.m[0][1] = (a.m[0][0]*b.m[0][1] + a.m[0][1]*b.m[1][1]) % mod;
    c.m[1][0] = (a.m[1][0]*b.m[0][0] + a.m[1][1]*b.m[1][0]) % mod;
    c.m[1][1] = (a.m[1][0]*b.m[0][1] + a.m[1][1]*b.m[1][1]) % mod;
    return c;
}

Mat lgput(Mat a , long long n) {
    if (n==0) {
        Mat c;
        c.m[0][0] = c.m[1][1] = 1;
        c.m[0][1] = c.m[1][0] = 0;
        return c;
    }
    Mat res = lgput(a, n/2);
    if (n%2==0) return inmult(res, res);
    return inmult(a, inmult(res, res));
}

int main()
{
    f >> n;
    Mat in;
    in.m[0][0] = 0; in.m[0][1] = in.m[1][0] = in.m[1][1] = 1;
    Mat k = lgput(in, n);
    g << k.m[1][0];
    return 0;
}