#include <iostream>
#include <cstring>
#define mod 666013

void prod(long long int A[][2],long long int B[][2],long long int R[][2]){
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                R[i][j] += (1LL * A[i][k] * B[k][j]) % mod;
            }
        }
    }
}

void fibonace(int p,long long int sol[][2]){
    long long int mat[2][2];
    mat[0][0] = 0;
    mat[0][1] = 1;
    mat[1][0] = 1;
    mat[1][1] = 1;
    long long int temp[2][2];
    for (int i = 0; (1 << i) <= p; i++) {
        if (p & (1 << i)) {
            memset(temp, 0, sizeof(temp));
            prod(sol, mat, temp);
            memcpy(sol, temp, sizeof(temp));
        }

        memset(temp, 0, sizeof(temp));
        prod(mat, mat, temp);
        memcpy(mat, temp, sizeof(mat));
    }
}

int main()
{
    long long int sol[2][2];

    sol[0][0] = 1;
    sol[0][1] = 0;
    sol[1][0] = 0;
    sol[1][1] = 1;
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    int p;

    std::cin >> p;
    fibonace(p-1,sol);
    std::cout << sol[1][1];
    return 0;
}