#include <bits/stdc++.h>

using namespace std;

const int MOD = 666013;

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

long long T[5][5], R[5][5], I[5][5];

void inmultire(long long A[][5], int I1, int J1, long long B[][5], int I2, int J2){
    int C[5][5];
    for(int i=1; i<=J1; ++i){
        for(int j=1; j<=I2; ++j){
            C[i][j] = 0;
            for(int k=1; k<=I2; ++k){
                C[i][j] += (A[i][k] * B[k][j]) % MOD;
                C[i][j] %= MOD;
            }
        }
    }
    for(int i=1; i<=J1; ++i){
        for(int j=1; j<=I2; ++j){
            A[i][j] = C[i][j];
        }
    }
}

void exp_rap(int b){
    for(int i=1; i<=2; ++i){
        for(int j=1; j<=2; ++j){
            if(i == j){
                I[i][j] = 1;
            }
            else{
                I[i][j] = 0;
            }
        }
    }
    T[1][1] = 0;
    T[1][2] = T[2][1] = T[2][2] = 1;
    R[1][1] = 1;
    R[1][2] = 1;
    while(b > 0){
        if(b % 2 == 1){
            inmultire(I, 2, 2, T, 2, 2);
        }
        inmultire(T, 2, 2, T, 2, 2);
        b /= 2;
    }
    inmultire(R, 1, 2, I, 2, 2);
}
int main()
{
    int N;
    fin >> N;
    exp_rap(N - 2);
    fout << R[1][2] << '\n';
    return 0;
}