#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

void inmult(long long A[][3], long long B[][3])
{
    long long C[3][3] = {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] + A[i][k] * B[k][j]) % 666013;
    for(int i = 0 ; i < 2 ; i ++)
        for(int j = 0 ; j < 2 ; j ++)
            A[i][j] = C[i][j];
}

void putere(long long A[][3], long long B[][3],int n)
{
    B[0][0] = 0;
    B[0][1] = B[1][1] = B[1][0] = 1;
    while(n)
    {
        if(n % 2)
        {
            inmult(A, B);
        }
        inmult(B, B);
        n /= 2;
    }
}
int main(void)
{
    long long x, n, A[3][3], B[3][3];
    A[0][0] = A[1][1] = 1;
    A[0][1] = A[1][0] = 0;
    FILE *in;
    FILE *out;
    in = fopen("kfib.in", "r");
    out = fopen("kfib.out", "w");
    fscanf(in, "%lld", &n);
    putere(A, B, n);
    fprintf(out, "%lld", A[0][1]);
    return 0;
}