///circular
//unordered_
#include <bits/stdc++.h>
#define MOD 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long k,nr[5][5],ras[5][5];
void inm(long long a[][5],long long b[][5])
{
    int cp[5][5]= {0};
    for(int i=1; i<=2; i++)
        for(int j=1; j<=2; j++)
            for(int y=1; y<=2; y++)
            {
                cp[i][j]+=a[i][y]*b[y][j]%MOD;
                if(cp[i][j]>=MOD)
                    cp[i][j]%=MOD;
            }
    for(int i=1; i<=2; i++)
        for(int j=1; j<=2; j++)
            a[i][j]=cp[i][j];
}
void rid(long long put)
{
    while(put)
    {
        if(put%2==1)
            inm(ras,nr);
        inm(nr,nr);
        put/=2;
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    fin>>k;
    nr[1][2]=nr[2][1]=nr[2][2]=1;
    ras[1][1]=ras[2][2]=1;
    rid(k-3);
    cout<<(ras[2][1]+(ras[2][2]*2)%MOD)%MOD;
    return 0;
}