#include <bits/stdc++.h>
#define mod 666013
using namespace std;

ifstream f("kfib.in");
ofstream g ("kfib.out");

long long k;

struct mat {
    long long M[2][2];
};

mat mati={
    0,1,
    1,1
};

mat prod (mat A,mat B) {
    mat a;
    a.M[0][0]=(A.M[0][0]*B.M[0][0]%mod+A.M[0][1]*B.M[1][0]%mod)%mod;
    a.M[0][1]=(A.M[0][0]*B.M[0][1]%mod+A.M[0][1]*B.M[1][1]%mod)%mod;
    a.M[1][0]=(A.M[1][0]*B.M[0][0]%mod+A.M[1][1]*B.M[1][0]%mod)%mod;
    a.M[1][1]=(A.M[1][0]*B.M[0][1]%mod+A.M[1][1]*B.M[1][1]%mod)%mod;
    return a;
}

mat lgput(mat M,long long k) {
    if(k==1) {
        return M;
    }
    if(k%2==1) {
        return prod(M,lgput(M,k-1));
    }
    else {
        return prod(lgput(M,k/2),lgput(M,k/2));
    }
}
int main()
{
    f >> k;
    g << lgput(mati,k).M[1][0];
    return 0;
}