#include <bits/stdc++.h>

#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

#define cin fin
#define cout fout

ifstream fin ("kfib.in");
ofstream fout ("kfib.out");

const int MOD=666013;

int ident[2][2];
int mat[2][2];
int aux[2][2];
int fib[2][2];

void inmultire(int a[2][2],int b[2][2])
{
    int i,j,k;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
            aux[i][j]=0;
    for(i=0;i<2;i++)
    {
        for(j=0;j<2;j++)
        {
            for(k=0;k<2;k++)
                aux[i][j]=(aux[i][j]+1LL*a[i][k]*b[k][j])%MOD;
        }
    }
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
            ident[i][j]=aux[i][j];
}

void lgput(int b)
{
    if(b==0)
        return ;
    else
    {
        if(b%2==0)
        {
            lgput(b/2);
            inmultire(ident,ident);
        }
        else
        {
            lgput(b/2);
            inmultire(ident,ident);
            inmultire(mat,ident);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n,i,j,k;
    cin>>k;
    k--;
    for(i=0;i<2;i++)
        ident[i][i]=1;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
            if(i==0 && j==0)
                mat[i][j]=0;
            else
                mat[i][j]=1;
    fib[0][0]=0;
    fib[0][1]=1;
    lgput(k);
    inmultire(fib,ident);
    cout<<ident[0][1];
    return 0;
}