#include <iostream>
#include <fstream>

using namespace std;

const int mod=666013;

void copmat(int a[2][2],int b[2][2])
{
    for (int i=0; i<2; i++)
        for (int j=0; j<2; j++)
            a[i][j]=b[i][j];
}

void mult(int a[2][2],int b[2][2])
{
    int c[2][2]= {0,0,0,0};
    for (int i=0; i<2; i++)
        for (int j=0; j<2; j++)
            for (int k=0; k<2; k++)
                c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%mod;
    copmat(a,c);
}

int main()
{
    ifstream fin ("kfib.in");
    ofstream fout ("kfib.out");
    int k,c[2][2]= {1,1,0,0},z[2][2]= {1,1,1,0};
    fin>>k;
    k-=2;
    while(k>1)
        if (k%2==0)
        {
            mult(z,z);
            k/=2;
        }
        else
        {
            mult(c,z);
            k--;
        }
    mult(c,z);
    fout<<c[0][0];
    return 0;
}