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

typedef long long ll;

using namespace std;

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

ll fibo[2][2] = {{1,1},{1,0}};
ll sol[2][2] = {{1,0},{0,1}};

void multiply(ll A[2][2],ll B[2][2]){
    ll a = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % MAX;
    ll b = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % MAX;
    ll c = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % MAX;
    ll d = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % MAX;

    A[0][0] = a;
    A[0][1] = b;
    A[1][0] = c;
    A[1][1] = d;
}

void factorizare(int n){
    while(n){
        if(n % 2 == 0){
            multiply(fibo,fibo);
            n /= 2;
        }else{
            multiply(sol,fibo);
            n --;
        }
    }
}
int rez(int n){
    if(n == 2 || n == 1)
        return 1;
    if(!n)
        return 0;

    factorizare(n-1);
    return sol[0][0];
}

int putere(int a,int b){
    int rez = 1;
    while(b){
        if(b % 2 == 0){
            a *= a;
            b /= 2;
        }else{
            rez *= a;
            b--;
        }
    }
    return rez;
}

int main()
{
    int k;
    in>>k;
    out<<rez(k);
    return 0;
}