#include <iostream>
#include<fstream>
#define MOD 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long long n;
struct matrice
{
    long long a,b,c,d;
};
matrice z;
matrice m(matrice p)
{
    p.a%=MOD;
    p.b%=MOD;
    p.c%=MOD;
    p.d%=MOD;
    return p;
}
struct mat
{
    long long a,b;
};
matrice inmultire(matrice a,matrice b)
{
    matrice p;
    p.a=a.a*b.a+a.b*b.c;
    p.b=a.a*b.b+a.b*b.d;
    p.c=a.c*b.a+a.d*b.c;
    p.d=a.c*b.b+a.d*b.d;
    return m(p);
}
matrice exp(matrice a,long long p)
{
    if(p==1)
        return m(a);
    if(p%2==0)
        return m(exp(inmultire(a,a),p/2));
    else
        return m(inmultire(exp(a,p-1),a));
}
int main()
{
    f>>n;
    z.a=0;
    z.b=1;
    z.c=1;
    z.d=1;
    mat m;
    m.a=1;
    m.b=1;
    z=exp(z,n-1);
    g<<z.d;
}