#include <bits/stdc++.h>

using namespace std;

ifstream f("veverita.in");
ofstream g("veverita.out");

typedef long long ll;
const ll mod = 666013;
ll n, ans, sol;
typedef ll mare[5005] ;
mare A, B;
void atrib(mare A, ll m)
{
    A[0] = 0;
    while(m)
    {
        A[0]++;
        A[ A[0] ] = m % 10;
        m /= 10;
    }
}
void atribM(mare A, mare B) /// B = A
{
    for(int i = 0; i <= A[0]; ++i)
        B[i] = A[i];

}
void multi(mare A, mare B, mare C) /// C = A * B
{
    ll T = 0;
    C[0] = A[0] + B[0] - 1;
    for(int i = 1; i <= A[0] + B[0]; ++i)
        C[i] = 0;
    for(int i = 1; i <= A[0]; ++i)
        for(int j = 1; j <= B[0]; ++j)
            C[i + j - 1] += A[i] * B[j];
    for(int i = 1; i <= C[0]; ++i)
    {
        C[i] += T;
        T = C[i] / 10;
        C[i] %= 10;

    }
    if(T)
        C[ ++C[0] ] = T;
}
ll logpow(ll a, ll b)
{
    ll sol = 1;
    while(b)
    {
        if(b & 1)
            sol = (sol * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return sol;
}

void afisM(mare A)
{
    for(int i = A[0]; i >= 1; --i)
        g << A[i];
    g << '\n';
}

void expo(mare A, ll b)
{
    mare R, aux, aux2;
    atrib(R, 1);
    while(b)
    {
        if(b & 1)
        {
            multi(R, A, aux);
            atribM(aux, R);
        }
        atribM(A, aux);
        multi(A, aux, aux2);
        atribM(aux2, A);
        b >>= 1;
    }
    atribM(R, A);
}

void multint(mare A, ll x)
{
    ll T = 0;
    for(int i = 1; i <= A[0]; ++i)
    {
        A[i] = A[i] * x + T;
        T = A[i] / 10;
        A[i] %= 10;
    }
    while (T)
    {
        A[ ++A[0] ] = T % 10;
        T /= 10;
    }
}
int main()
{
    f >> n;
    if(n > 0)
    {
        if(n % 2 == 1)
        {
            ans = logpow(2, (n - 1) / 2);
            ans = (3 * ans) % mod;
        }
        else
        {
            ans = logpow(2, n / 2);
            ans = (2 * ans) % mod;
        }
        g << ans;
    }
    else
    {
        atrib(A, 2);
        if(n % 2 == 1)
        {
            expo(A, (n - 1) / 2);
            multint(A, 3);
            afisM(A);
        }
        else
        {
            expo(A, (n) / 2);
            multint(A, 2);
            afisM(A);
        }
    }
    f.close();
    g.close();
    return 0;
}