#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 mat0={
    1,0,
    0,1
};
mat mati={
    1,1,
    1,0
};
mat prod (mat A,mat B)
{
    mat a;
    a.M[0][0]=(A.M[0][0]*B.M[0][0]+A.M[0][1]*B.M[1][0])%mod;
    a.M[0][1]=(A.M[0][0]*B.M[0][1]+A.M[0][1]*B.M[1][1])%mod;
    a.M[1][0]=(A.M[1][0]*B.M[0][0]+A.M[1][1]*B.M[1][0])%mod;
    a.M[1][1]=(A.M[1][0]*B.M[0][1]+A.M[1][1]*B.M[1][1])%mod;
    return a;
}
mat lgput(mat M,long long k)
{
    if(k==0)
        return mat0;
    if(k%2==0)
        return lgput(prod(M,M),k/2);
    return prod(M,lgput(prod(M,M),k/2));
}
int main()
{
    f>>k;
    g<<lgput(mati,k).M[0][1];
    return 0;
}