#include <bits/stdc++.h>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
#define MOD 666013
typedef long long mat[2][2];

long long n;

void mult(mat &x, mat y)
{
    mat rez;
    rez[0][0] = ((x[0][0]*y[0][0])%MOD + (x[0][1]*y[1][0])%MOD)%MOD;
    rez[0][1] = ((x[0][0]*y[0][1])%MOD + (x[0][1]*y[1][1])%MOD)%MOD;
    rez[1][0] = ((x[1][0]*y[0][0])%MOD + (x[1][1]*y[1][0])%MOD)%MOD;
    rez[1][1] = ((x[1][0]*y[0][1])%MOD + (x[1][1]*y[1][1])%MOD)%MOD;
    x[0][0]=rez[0][0];
    x[0][1]=rez[0][1];
    x[1][0]=rez[1][0];
    x[1][1]=rez[1][1];
}

void put()
{
    mat b={{1,1},{1,0}},
        a={{1,0},{0,1}};
    while(n>0){
        if(n%2==1)
            mult(a,b);
        mult(b,b);
        n>>=1;
    }
    fout<<a[0][0]%MOD;
}

int main()
{
    fin>>n;
    n--;
    put();
}