#include <iostream>
#include <fstream>
#define MAX 10000000

using namespace std;

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

int v[MAX];

int fib(int n) {
    if(n<MAX && v[n]!=0)
        return v[n];
    if(n == 1 || n == 2)
        return 1;
    if(n<MAX){
    v[n]=(fib(n-1)+fib(n-2))%666013;

    return v[n];
    }
    else
        return (fib(n-1)+fib(n-2))%666013;
}

int main()
{
    int n;
    in>>n;
    out<<fib(n)%666013;

    return 0;
}