#include<bits/stdc++.h>

using namespace std;

const int MOD = 666013;
long long k, m[3][3], v[3][3], c[3][3];;
short int n = 2;

void ridput()
{
    m[0][0] = 0;
    m[0][1] = 1;
    m[1][0] = 1;
    m[1][1] = 1;
    v[0][1] = 1;

    while(k)
    {
        if(k % 2 == 1)
        {
            for(int i = 0; i < n; i++)
            {
                for(int j = 0; j < n; j++)
                {
                    c[i][j] = 0;
                    for(int l = 0; l < n; l++)
                    {
                        c[i][j] += v[i][l] * m[l][j];
                        c[i][j] %= MOD;
                    }
                }
            }

            for(int i = 0; i < n; i++)
                for(int j = 0; j < n; j++)
                    v[i][j] = c[i][j];
        }

        k = k >> 1;

        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                c[i][j] = 0;
                for(int l = 0; l < n; l++)
                {
                    c[i][j] += m[i][l] * m[l][j];
                    c[i][j] %= MOD;
                }
            }
        }

        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                m[i][j] = c[i][j];
    }

    cout << v[0][0];
}

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);

    cin >> k;

    ridput();
}