#include <iostream>
#include <fstream>
using namespace std;
const int mod=666013;

void inm (long long a[3][3],long long b[3][3])
{
    int aux[3][3]={0};
        for (int i=0; i<2; i++)
            for (int j=0; j<2; j++)
                for (int k=0; k<2; k++)
                    aux[i][j]=1LL*(aux[i][j]+a[i][k]*b[k][j])%mod;
    for (int i=0; i<3; i++)
            for (int j=0; j<3; j++)
                a[i][j]=aux[i][j];
}

int main()
{
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    int n;
    f>>n;
    long long a[3][3]={{0,1}, {1,1}}, b[3][3]={{0,1}, {1,1}};
    n-=2;
    while (n)
    {
        if (n%2==1)
            inm(b, a);
        inm(a,a);
    n/=2;
    }
    g<<1LL*(b[0][0]+b[0][1])%mod;
    return 0;
}