#include <bits/stdc++.h>
using namespace std;
///=================
#define swap(a,b) a^=b^=a^=b
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
const string file_name = "kfib";
ifstream fin(file_name + ".in");
ofstream fout(file_name + ".out");

long long n, a = 1, b = 1, fn = 0, poz = 2;

void solve1();
int main()
{
    fin >> n;

    solve1();

    fout << fn;

    return 0;
}

void solve1(){
    if(n == 1)
        fn = 1, exit(0);
    if(n == 2)
        fn = 1, exit(0);

    while(true){
        if(poz == n){
            fn = b;
            return ;
        }
        int aux = b;
        b = a + b;
        a = aux;
        a %= 666013;
        b %= 666013;
        poz++;
    }
}