#include <iostream>
#include <fstream>
#include <vector>

#define SIZE 2
#define ll long long

using namespace std;

const int M = 666013;

vector<vector<ll>> z{
    {0, 1},
    {1, 1}
};

vector<vector<ll>> matrix_multiply(vector<vector<ll>> a, vector<vector<ll>> b)
{
    vector<vector<ll>> v(2, vector<ll>(2, 0));

    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++)
            {
                v[i][j] = ((v[i][j] % M) + (a[i][k] * b[k][j]) % M) % M;
            }

    return v;
}

ll kfib(vector<vector<ll>> z, ll p)
{
    if(p == -1)
        return 0;
    if(p == 0)
        return 1;
    
    vector<vector<ll>> x{
    {1, 0},
    {0, 1}
    };

    while(p > 1)
    {
        if(p % 2)
        {
            x = matrix_multiply(x, z);
            p--;
        }
        z = matrix_multiply(z, z);
        p = p / 2;
    }

    vector<vector<ll>> ans(2, vector<ll>(2));

    ans = matrix_multiply(z, x);
    
    return ans[1][1];
}

int main(void)
{
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");

    int k;
    fin >> k;

    fout << kfib(z, k - 1);

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