#include<fstream>
#include<cmath>
#define MOD 666013

using namespace std;
int mat[3][3];
int sol[3][3];

void init(int x[][3] ,int k){
    x[0][0] = k;
    x[0][1] = k;
    x[1][0] = k;
    x[1][1] = k;
}

void init_mat(int x[][3] ,int y[][3]){
    x[0][0] = y[0][0];
    x[0][1] = y[0][1];
    x[1][0] = y[1][0];
    x[1][1] = y[1][1];
}

void inm(int a[][3], int b[][3])
{
    int c[3][3];
    init(c,0);
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % MOD;
    init_mat(a,c);
}

void power(int sol[][3], int mat[][3],int n)
{
    while(n>0){
        if (n%2!=0){
            inm(sol, mat);
        }
        inm(mat, mat);
        n=n/2;
    }
}

int main()
{
    int n = 0;
    ifstream fi("kfib.in");
    fi>>n;
    fi.close();
    mat[0][0] = 0;
    mat[0][1] = 1;
    mat[1][0] = 1;
    mat[1][1] = 1;
    sol[0][0] = 1;
    sol[0][1] = 0;
    sol[1][0] = 0;
    sol[1][1] = 1;
    power(sol, mat,n);
    ofstream fo("kfib.out");
    fo<<sol[0][1];
    fo.close();
    return 0;
}