#include <fstream>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
#define mod 666013

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

void pow(long long B[2][2], int n, long long R[2][2]){
    while(n > 0){
        if(n % 2 == 1)
            prod(R,B);
        prod(B,B);
        n /= 2;
    }
}

int main()
{
    int k;
    long long rez;
    f >> k;
    long long P[2][2] = {{1, 0}, {0, 1}};
    long long B[2][2] = {{0, 1}, {1, 1}};
    pow(B,k,P);
    rez = P[0][1] % mod;
    g << rez;
    return 0;
}