#include <iostream>
#include <cstdio>
using namespace std;
long long n,a[3][3],d[3][3],nr[50],fib[3][3],c[3][3],nr1=0;
void citire()
{
    scanf("%lld",&n);
    long long m,q;
    m=1;
    q=2*n;
    while(m<=q)
    {
        m*=2;
    }
    m/=2;
    while(m!=0)
    {
        if(q>=m)
            {
                q=q-m;
                nr[nr1]=1;
            }
        else
            nr[nr1]=0;
        m/=2;
        nr1++;
    }
    fib[1][1]=1;
    fib[1][2]=1;
    fib[2][1]=1;
    fib[2][2]=0;
}
void cerinta()
{
    d[1][1]=1;
    d[1][2]=0;
    d[2][1]=0;
    d[2][2]=1;
    if(nr[nr1-1]==1)
    {
        d[1][1]=fib[1][1];
        d[1][2]=fib[1][2];
        d[2][1]=fib[2][1];
        d[2][2]=fib[2][2];
    }
    for(int i=nr1-2;i>=0;i--)
    {
        if(nr[i]==1)
        {
    c[1][1]=(d[1][1]*fib[1][1]+d[1][2]*fib[2][1])%666013;
    c[1][2]=(d[1][1]*fib[1][2]+d[1][2]*fib[2][2])%666013;
    c[2][1]=(d[2][1]*fib[1][1]+d[2][2]*fib[2][1])%666013;
    c[2][2]=(d[2][1]*fib[1][2]+d[2][2]*fib[2][2])%666013;
        d[1][1]=c[1][1];
        d[1][2]=c[1][2];
        d[2][1]=c[2][1];
        d[2][2]=c[2][2];
        }
        c[1][1]=(fib[1][1]*fib[1][1]+fib[1][2]*fib[2][1])%666013;
    c[1][2]=(fib[1][1]*fib[1][2]+fib[1][2]*fib[2][2])%666013;
    c[2][1]=(fib[2][1]*fib[1][1]+fib[2][2]*fib[2][1])%666013;
    c[2][2]=(fib[2][1]*fib[1][2]+fib[2][2]*fib[2][2])%666013;
        fib[1][1]=c[1][1];
        fib[1][2]=c[1][2];
        fib[2][1]=c[2][1];
        fib[2][2]=c[2][2];
    }
    printf("%ld",d[1][2]);
}
int main()
{
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    citire();
    cerinta();
    //cout << "Hello world!" << endl;
    return 0;
}