#include <fstream>
#define mod 666013
using namespace std;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
int k;
struct matrice
{
    long long a,b,c,d;
    matrice operator* (matrice m)
    {
        matrice ans;
        ans.a = (a*m.a + b*m.c)%mod;
        ans.b = (a*m.b + b*m.d)%mod;
        ans.c = (c*m.a + d*m.c)%mod;
        ans.d = (c*m.b + d*m.d)%mod;
        return ans;
    }
    matrice(long long a, long long b, long long c, long long d)
    {
        this->a = a;
        this->b = b;
        this->c = c;
        this->d = d;
    }
    matrice() {}

};
matrice putere(int k)
{
    if(k==1)
        return matrice(0,1,1,1);

    if(k%2)
        return putere(k/2)*putere(k/2)*matrice(0,1,1,1);

    return putere(k/2)*putere(k/2);
}
int main()
{
    fin>>k;
    if(k==0)
    {
        fout<<0;
        return 0;
    }
    if(k==1)
    {
        fout<<1;
        return 0;
    }
    matrice ans = putere(k-1);
    fout<<ans.d;
    return 0;
}