#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
#define mod 666013
#define MAT AB[i][j]
void inmultire_mat22(long long int A[2][2], long long int B[2][2])
{
    long long int AB[2][2];
    for (int i=0;i<2;i++)
        for(int j=0;j<2;j++){
                 MAT=0;
            for(int l=0;l<2;l++)
                MAT+=A[i][l]*B[l][j]%mod;
            MAT%=mod;
    }
    for (int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            A[i][j]=MAT;

}

long long int mat_fib[2][2]={{0,1}, {1,1}};
long long int t_fib[2][2]={{0,1},{1,1}};

int main()
{

    long long int k;
    fin>>k;
    while (k){
        if(k%2==1)
        inmultire_mat22(t_fib,mat_fib);
        inmultire_mat22(mat_fib,mat_fib);
        k/=2;
    }
    fout << t_fib[0][0];
    return 0;


}
/*void inmultire_mat12(int A[1][2], int B[2][2])
{
    long long int  AB[1][2];
    for (int i=0;i<1;i++)
        for(int j=0;j<2;j++){
                 AB[i][j]=0;
            for(int l=0;l<2;l++)
                AB[i][j]+=A[i][l]*B[l][j];
            AB[i][j]%=mod;
    }
    for (int i=0;i<1;i++)
        for(int j=0;j<2;j++)
            A[i][j]=AB[i][j];

} */