#include <bits/stdc++.h>
#define MOD 666013
#define ull unsigned long long

using namespace std;

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

long long A[3][3];
long long B[3][3];

void init(){
    A[1][1] = 0;
    A[1][2] = 1;
    A[2][1] = 1;
    A[2][2] = 1;
    B[1][1] = 1;
    B[1][2] = 0;
    B[2][1] = 0;
    B[2][2] = 1;
}

void putlog(int a){
    long long aux[3][3];
    while(a){
        if(a%2 == 1){
            aux[1][1] = (B[1][1]*A[1][1])%MOD + (B[1][2]*A[2][1])%MOD;
            aux[1][2] = (B[1][1]*A[1][2])%MOD + (B[1][2]*A[2][2])%MOD;
            aux[2][1] = (B[2][1]*A[1][1])%MOD + (B[2][2]*A[2][1])%MOD;
            aux[2][2] = (B[2][1]*A[1][2])%MOD + (B[2][2]*A[2][2])%MOD;
            B[1][1] = (aux[1][1])%MOD;
            B[1][2] = (aux[1][2])%MOD;
            B[2][1] = (aux[2][1])%MOD;
            B[2][2] = (aux[2][2])%MOD;
        }
        a /= 2;
        aux[1][1] = (A[1][1]*A[1][1])%MOD + (A[1][2]*A[2][1])%MOD;
        aux[1][2] = (A[1][1]*A[1][2])%MOD + (A[1][2]*A[2][2])%MOD;
        aux[2][1] = (A[2][1]*A[1][1])%MOD + (A[2][2]*A[2][1])%MOD;
        aux[2][2] = (A[2][1]*A[1][2])%MOD + (A[2][2]*A[2][2])%MOD;
        A[1][1] = (aux[1][1])%MOD;
        A[1][2] = (aux[1][2])%MOD;
        A[2][1] = (aux[2][1])%MOD;
        A[2][2] = (aux[2][2])%MOD;
    }
}

int main()
{
    init();
    int n;
    fin>>n;
    putlog(n+1);
    fout<<(B[1][1])%MOD<<'\n';
    return 0;
}