#include <iostream>
#include <fstream>

using namespace std;
typedef unsigned long long mat[2][2];
#define MOD 666013

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

void inm (mat a, mat b, mat c)
{
    mat d;
    d[0][0]=((a[0][0]*b[0][0])%MOD+(a[0][1]*b[1][0])%MOD)%MOD;
    d[0][1]=((a[0][0]*b[0][1])%MOD+(a[0][1]*b[1][1])%MOD)%MOD;
    d[1][0]=((a[1][0]*b[0][0])%MOD+(a[1][1]*b[1][0])%MOD)%MOD;
    d[1][1]=((a[1][0]*b[0][1])%MOD+(a[1][1]*b[1][1])%MOD)%MOD;
    c[0][0]=d[0][0]; c[0][1]=d[0][1];
    c[1][0]=d[1][0]; c[1][1]=d[1][1];
}


void Alan(mat a,int n, mat b)
{
    if(n==0){b[0][0]=b[1][1]=1;
             b[0][1]=b[1][0]=0;}
    else{mat aux;
         Alan(a,n/2,aux);
         inm(aux,aux,b);
         if(n%2)inm(b,a,b);
        }
}

int k;
int main()
{
    fin>>k;
    mat a,b;
    a[0][0]=0;
    a[1][0]=a[0][1]=a[1][1]=1;
    Alan(a,k-1,b);
    fout<<b[1][1];


    fin.close(); fout.close();
    return 0;
}