#include <fstream>
#include <cmath>

using namespace std;

ifstream in("kfib.in");
ofstream out("kfib.out");

const int mod=666013;

class Mat4
{
public:
    long long mat[2][2];
    
    Mat4(long long a, long long b, long long c, long long d)
    {
        mat[0][0]=a;
        mat[0][1]=b;
        mat[1][0]=c;
        mat[1][1]=d;
    }
    
    Mat4(const Mat4 &other) {
        *this = other;
    }
    
    Mat4 operator *(Mat4 other)
    {
        Mat4 rasp(0, 0, 0, 0);
        rasp.mat[0][0]=(mat[0][0]*other.mat[0][0]+mat[0][1]*other.mat[1][0])%mod;
        rasp.mat[0][1]=(mat[0][0]*other.mat[0][1]+mat[0][1]*other.mat[1][1])%mod;
        rasp.mat[1][0]=(mat[1][0]*other.mat[0][0]+mat[1][1]*other.mat[1][0])%mod;
        rasp.mat[1][1]=(mat[1][0]*other.mat[0][1]+mat[1][1]*other.mat[1][1])%mod;
        return rasp;
    }
    
    Mat4 operator =(const Mat4 &other) {
        mat[0][0]=other.mat[0][0];
        mat[0][1]=other.mat[0][1];
        mat[1][0]=other.mat[1][0];
        mat[1][1]=other.mat[1][1];
    }
    
    long long *operator [](int i) {
        return mat[i];
    }
};

Mat4 lgput(Mat4 mat, int k)
{
    if(k==0)
    {
        return Mat4(1, 0, 0, 1);
    }
    if(k%2==0)
    {
        Mat4 matrice=lgput(mat, k/2);
        return matrice*matrice;
    }
    else
    {
        return lgput(mat,k-1)*mat;
    }
}

int main()
{
    int k;
    in>>k;
    Mat4 fib1(1, 1, 0, 0);
    Mat4 matrice(0, 1, 1, 1);
    Mat4 putere_matrice=lgput(matrice, k-1);
    Mat4 rasp = matrice*putere_matrice;
    //out<<putere_matrice[0][0] << ' ' << putere_matrice[0][1]<< '\n' <<putere_matrice[1][0]<< ' '<< putere_matrice[1][1];
    out<<rasp[0][1];
}