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

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

}
int mat_fib[2][2];
int t_fib[1][2];

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


}