#include <fstream>
#define MOD 666013

using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");

long long k, c[2][2], a[2][2];

void multmat(long long a[2][2], long long b[2][2])
{
    long long rez[2][2]={0};

    for(int i=0; i<=1; i++)
        for(int j=0; j<=1; j++)
            for(int k=0; k<=1; k++){
                rez[i][j] += a[i][k] * b[k][j];
                rez[i][j] %= MOD;
            }

    for(int i=0; i<=1; i++) for(int j=0; j<=1; j++)
        a[i][j] = rez[i][j];
}

void lgpow(long long p)
{
    while(p)
    {
        if((p&1)==0)
        {
            p>>=1;
            multmat(c,c);
        }
        else
        {
            p--;
            multmat(a,c);
        }
    }
}

int main()
{
    in>>k;

    c[0][0]=0; c[0][1]=1;
    c[1][0]=1; c[1][1]=1;

    a[0][0]=1; a[0][1]=0;
    a[1][0]=0; a[1][1]=1;

    lgpow(k-1);

    out<<a[1][1];

    return 0;
}