#include <bits/stdc++.h>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
#define int long long
const int MOD = 666013;

void multiply(int A[2][2], int B[2][2])
{
    int temp[2][2] = {{0, 0},
                      {0, 0}};
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++)
                temp[i][j] = (temp[i][j] + A[i][k] * B[k][j]) % MOD;
    memcpy(A, temp, sizeof(temp));
}

void power(int A[2][2], int exp)
{
    int ans[2][2] = {{1, 0},
                     {0, 1}};
    int base[2][2] = {{A[0][0], A[0][1]},
                      {A[1][0], A[1][1]}};
    while(exp != 0)
    {
        if(exp % 2 == 1)
            multiply(ans, base);
        multiply(base, base);
        exp /= 2;
    }
    memcpy(A, ans, sizeof(ans));
}

signed main()
{
    int k;
    fin >> k;
    if(k == 0)
        fout << 0;
    else
    {
        int A[2][2] = {{0, 1},
                       {1, 1}};
        power(A, k - 1);
        fout << A[1][1];
    }

    fin.close();
    fout.close();
    return 0;
}