#include <fstream>
#include <vector>

using namespace std;

ifstream cin("kfib.in");
ofstream cout("kfib.out");

const int MOD = 666013;

int N;

struct Matrix
{

    int n, m;
    int a[5][5];

    Matrix(int nn, int mm, vector <int> vals)
    {
        for(int i = 0; i < 5; i++)
            for(int j = 0; j < 5; j++)
                a[i][j] = 0;

        n = nn, m = mm;

        int k = 0;
        for(int i = 1; i <= nn; i++)
            for(int j = 1; j <= mm; j++)
                a[i][j] = vals[k++];
    }

    Matrix(int nn, int mm)
    {
        for(int i = 0; i < 5; i++)
            for(int j = 0; j < 5; j++)
                a[i][j] = 0;

        n = nn, m = mm;
    }

    Matrix operator * (const Matrix other) const
    {
        Matrix ans(n, other.m);

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= other.m; j++)
            {
                long long f = 0;

                for(int k = 1; k <= m; k++)
                    f += 1LL * a[i][k] * other.a[k][j];

                ans.a[i][j] = f % MOD;
            }

        return ans;
    }
};

Matrix lgPut(Matrix base, int exp)
{
    vector <int> I; I.push_back(1), I.push_back(0), I.push_back(0), I.push_back(1);
    Matrix ans(2, 2, I), aux = base;

    for(int i = 1; i <= exp; i <<= 1)
    {
        if(i & exp)
            ans = ans * aux;

        aux = aux * aux;
    }

    return ans;
}

int main()
{
    cin >> N;

    if(N <= 1)
    {
        cout << N << '\n';
        return 0;
    }

    vector <int> a; a.push_back(0), a.push_back(1);
    Matrix A(1, 2, a);

    vector <int> z; z.push_back(0), z.push_back(1), z.push_back(1), z.push_back(1);
    Matrix Z(2, 2, z);

    Z = lgPut(Z, N);
    A = A * Z;

    cout << A.a[1][1] << '\n';

    return 0;
}