#include <iostream>
#include <fstream>
using namespace std; //1 1 2 3 5 ...
const long long mod = 666013;
void szorzas(long long A[2][2], long long B[2][2], long long rez[2][2])
{

    for(long long i=0; i<=1; i++)
    {
        for(long long j=0; j<=1; j++)
        {
            rez[i][j] = 0;
            for(long long k=0; k<=1; k++)
                rez[i][j] = (rez[i][j] + (A[i][k]*B[k][j])%mod)%mod;
        }
    }
}
void log_hatvany(long long Z[2][2], long long x, long long Zx[2][2])
{
    if(x==0)
    {
        Zx[0][0] = Zx[1][1] = 1;
        Zx[0][1] = Zx[1][0] = 0;
    }
    else if(x%2==0)
    {
        long long temp[2][2] = {0};
        szorzas(Z,Z,temp);
        log_hatvany(temp,x/2,Zx);
    }
    else
    {
        long long temp[2][2] = {0};
        long long temp2[2][2] = {0};
        szorzas(Z,Z,temp);
        log_hatvany(temp,x/2,temp2);
        szorzas(Z,temp2,Zx);
    }
}
int main()
{
    ifstream in("kfib.in");
    ofstream out("kfib.out");
    long long Z[2][2]={0,1,1,1};
    long long k;
    in>>k;
    //cin >> k;
    long long Zx[2][2];
    log_hatvany(Z,k,Zx);
    out << Zx[0][1];
    return 0;
}