#include <iostream>
#include <fstream>
#define mod 666013
using namespace std;

struct matrice {
long long a,b,c,d;
}I2,m;

matrice inmultire(matrice p,matrice q)
{
    matrice r;
    r.a=(p.a*q.a + p.b*q.c)%mod;
    r.b=(p.a*q.b + p.b*q.d)%mod;
    r.c=(p.c*q.a + p.d*q.c)%mod;
    r.d=(p.c*q.b + p.d*q.d)%mod;
    return r;
}

matrice putereMatrice(matrice p,int exponent)
{
    if(exponent==0)
        return I2;
    if(exponent==1)
        return p;
    if(exponent%2==0)
    {
        matrice q;
        q=putereMatrice(p,exponent/2);
        return inmultire(q,q);
    }
    return inmultire(p,putereMatrice(p,exponent-1));
}

int main()
{
    freopen("kfib.in","rt",stdin);
    freopen("kfib.out","wt",stdout);

    int k;
    cin>>k;
    m.a=0;
    m.b=1;
    m.c=1;
    m.d=1;
    I2.a=1;
    I2.d=1;
    m=putereMatrice(m,k-1);
    cout<<m.d<<'\n';


    return 0;
}