#include <iostream>
#define MOD 666013
#include <fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int z[2][2]={0,1,1,1};
int n;
int fibo[2][2];
int m[2][2];
void inmultire (int a[][2], int b[][2]) {
    int a2[2][2];
    a2[0][0]=a[0][0];
    a2[0][1]=a[0][1];
    a2[1][0]=a[1][0];
    a2[1][1]=a[1][1];
    int b2[2][2];
    b2[0][0]=b[0][0];
    b2[0][1]=b[0][1];
    b2[1][0]=b[1][0];
    b2[1][1]=b[1][1];
    a[0][0]=((long long)a2[0][0] * b2[0][0] % 666013 + (long long)a2[0][1] * b2[1][0] % 666013)% 666013 ;
    a[0][1]=((long long)a2[0][0] * b2[0][1] % 666013 + (long long)a2[0][1] * b2[1][1] % 666013)% 666013 ;
    a[1][0]=((long long)a2[1][0] * b2[0][0] % 666013 + (long long)a2[1][1] * b2[1][0] % 666013)% 666013 ;
    a[1][1]=((long long)a2[1][0] * b2[0][1] % 666013 + (long long)a2[1][1] * b2[1][1] % 666013)% 666013 ;
}
void ridicare(int n) {
    while (n>0) {
        if (n%2==1) {
            inmultire(fibo,m);
        }
        inmultire(m,m);
        n=n/2;
    }
}

//Z^n=(Fn+1 Fn)
//    (Fn Fn-1)
int main()
{
    fin>>n;
    m[0][0]=1;
    m[0][1]=1;
    m[1][0]=1;
    m[1][1]=0;
    fibo[0][0]=1;
    fibo[0][1]=0;
    fibo[1][0]=0;
    fibo[1][1]=1;
    ridicare(n);
    fout << fibo[1][0];
    return 0;
}