#include <iostream>
#include <fstream>
using namespace std;

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


class Matrix
{
public:
    long long a, b;
    long long c, d;
    Matrix(int A, int B, int C, int D)
    {
        a = A; b = B; c = C; d = D;
    }
    Matrix(const Matrix& mat)
    {
        a = mat.a; b = mat.b; c = mat.c; d = mat.d;
    }

    inline Matrix operator * (const Matrix& other) const
    {
        return Matrix((a * other.a + b * other.c) % 666013, (a * other.b + b * other.d) % 666013, (c * other.a + d * other.c) % 666013, (c * other.b + d * other.d) % 666013);
    }
    
    static Matrix Pow(Matrix a, int n)
    {
        if (n == 1)
        {
            return a;
        }

        Matrix b(a);
        if (n % 2 == 1)
        {
            b = Pow (a, n - 1);
            return a * b;
        }
        else
        {
            b = Pow(a, n / 2);
            return b * b;
        }
    }
};


const Matrix svepsMat(0, 1, 1, 1);
const Matrix A(0, 1, 0, 0);

int main()
{
    int n;
    fin >> n;

    Matrix B = Matrix::Pow(svepsMat, n); 
    fout << (A * B).a ;
}