#include <bits/stdc++.h>

#define input "kfib.in"
#define output "kfib.out"
#define MOD 666013

using namespace std;

ifstream in(input);
ofstream out(output);

class matrix
{
    public:
        int N, M;
        unsigned long long dp[3][3];
};

matrix operator*(matrix a, matrix b)
{
    matrix c;
    c.N = a.N, c.M = b.M;
    memset(c.dp, 0, sizeof c.dp);
    for(int i = 1; i <= a.N; i++)
        for(int j = 1; j <= c.M; j++)
            for(int k = 1; k <= a.M; k++)
                c.dp[i][j] = (c.dp[i][j] + (a.dp[i][k] * b.dp[k][j]) % MOD) % MOD;
    return c;
}

matrix lg_exp(matrix a, int exp)
{
    if(exp == 0)
    {
        a.dp[1][1] = a.dp[2][2] = 1;
        a.dp[1][2] = a.dp[2][1] = 0;
        return a;
    }
    if(exp == 1) return a;
    if(exp % 2) return a * lg_exp(a, exp - 1);
    return lg_exp(a * a, exp / 2);
}

int K;

void Solve()
{
    in >> K;
    if(K == 0)
    {
        out << 0;
        return;
    }
    matrix Z;
    Z.N = 2, Z.M = 2;
    Z.dp[1][1] = 0, Z.dp[1][2] = Z.dp[2][1] = Z.dp[2][2] = 1;
    Z = lg_exp(Z, K - 1);
    matrix A;
    A.N = 1, A.M = 2;
    A.dp[1][1] = 0, A.dp[1][2] = 1;
    A = A * Z;
    out << A.dp[1][2] << "\n";
}

int main()
{
    Solve();
    return 0;
}