#include <iostream>

using namespace std;

#define MOD 666013

void InmultireMatrici(long long A[2][2], long long B[2][2]){
    long long C[2][2];
    C[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % MOD;
    C[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % MOD;
    C[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % MOD;
    C[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % MOD;
    A[0][0] = C[0][0];
    A[0][1] = C[0][1];
    A[1][0] = C[1][0];
    A[1][1] = C[1][1];
}

void InmultireM(long long M[1][2], long long B[2][2]){
    long long C[1][2];
    C[0][0] = (M[0][0]*B[0][0] + M[0][1]*B[1][0]) % MOD;
    C[0][1] = (M[0][0]*B[0][1] + M[0][1]*B[1][1]) % MOD;
    M[0][0]=C[0][0]; 
    M[0][1]=C[0][1];
}

int main(){
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    int k;
    cin >> k;
    long long Z[2][2] = {{0,1},{1,1}};
    long long I[2][2] = {{1,0},{0,1}};
    k--;
    while(k){
        if(k % 2 == 1)
            InmultireMatrici(I,Z);
        InmultireMatrici(Z,Z);
        k/=2;
    }

    long long M[1][2] = {{0,1}};
    InmultireM(M,I);

    cout << M[0][1];
    return 0;
}