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

#define MAX 1000000
#define MOD 666013

// a a  b b
// a a  b b


void inmultire_matrice(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];
}

int main()
{
    FILE *file = fopen("kfib.in", "r");
    FILE *output = fopen("kfib.out", "w");
    if (file == NULL)
    {
        fprintf(stderr, "Eroare deschidere fisier intrare.\n");
        return 1;
    }
    if (output == NULL)
    {
        fprintf(stderr, "Eroare deschidere fisier iesire.\n");
        fclose(file);
        return 1;
    }
    long long n;
    fscanf(file,"%lld", &n);
    if(n==0)
    {
        fprintf(output,"0\n");
    }
    else
    {
        long long rez[2][2]={{1,0},{0,1}}; // matricea identitate
        long long Z[2][2]={{0,1},{1,1}}; //matricea Z
        while(n>0)
        {
            if(n%2==1)
            {
                inmultire_matrice(rez,Z);
            }
            inmultire_matrice(Z,Z);
            n=n/2;
        }
        fprintf(output,"%lld\n", rez[0][1]);
    }
    fclose(file);
    fclose(output);
    return 0;
}