#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define enter cout << '\n'

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <pii> vii;
typedef vector <ll> vl;
typedef vector <pll> vll;
typedef queue <int> qi;
typedef queue <pii> qii;
typedef queue <ll> ql;
typedef queue <pll> qll;

const int INF = 0x3f3f3f3f;
const int MOD = 666013;
const int EPSILON = 0.0000000001;
const int NMAX = 2e5 + 5;

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

void matrix_mult(long long A[][3], long long B[][3])
{
    long long R[3][3];
    memset(R, 0, sizeof(R));

    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            for (int k = 0; k < 2; ++k)
                R[i][j] = (R[i][j] + A[i][k] * B[k][j]) % MOD;

    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            A[i][j] = R[i][j];
}

void matrix_pow(long long A[][3], long long O[][3], int p)
{
    if (p == 1) return;
    if (p % 2 == 0)
    {
        matrix_pow(A, O, p / 2);
        matrix_mult(A, A);
        return;
    }
    matrix_pow(A, O, p / 2);
    matrix_mult(A, A);
    matrix_mult(A, O);
}

int k;
long long M[3][3], N[3][3], O[3][3], P[3][3];

int main()
{
    M[0][1] = 1;
    N[0][1] = N[1][0] = N[1][1] = 1;
    O[0][1] = O[1][0] = O[1][1] = 1;

    fin >> k;
    matrix_pow(N, O, k - 1);
    matrix_mult(M, N);

    fout << M[0][1];

    return 0;
}