#include <bits/stdc++.h>
#define M 666013
using namespace std;
ifstream fin(".in");
ofstream fout(".out");

struct matrix{
    long long m[2][2];
    matrix(){ m[0][0] = m[0][1] = m[1][0] = m[1][1] = 0; }

    matrix operator*(const matrix& b){
        matrix c;
        for(long long i = 0; i < 2; ++i)
            for(long long j = 0; j < 2; ++j)
                for(long long k = 0; k < 2; ++k)
                    c.m[i][j] = (c.m[i][j] + 1LL * m[i][k] * b.m[k][j]) % M;
        return c;
    }
};

matrix f, unu;
matrix powow(matrix x, long long p){
    matrix y;
    y.m[0][0] = y.m[1][1] = 1;
    for(long long i = 0; (1 << i) <= p; ++i){
        if(p & (1 << i))
            y = y * x;
        x = x * x;
    }
    return y;
}
int main()
{
    long long n;
    fin >> n;
    f.m[0][1] = 1;
    unu.m[0][1] = unu.m[1][0] = unu.m[1][1] = 1;

    unu = powow(unu, n);

    f = f * unu;
    cout << f.m[0][0];
    return 0;
}