#include <iostream>
#include <fstream>
#define MOD 666013

using namespace std;

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

int n;
int a[4][4];
int i2[4][4];

void mult(int a[4][4], int b[4][4])
{
    long long c[4][4]={0};
    for (int i = 1; i <= 2; i++)
        for (int j = 1; j <= 2; j++)
            for (int k = 1; k <= 2; k++)
            {
                c[i][j]+=1LL*a[i][k]*b[k][j];
                c[i][j]%=MOD;
            }

    for (int i = 1; i <= 2; i++)
        for (int j = 1; j <= 2; j++)
            a[i][j]=c[i][j]%MOD;
}

int main()
{
    f >> n;
    a[1][1]=1; a[1][2]=1;
    a[2][1]=1; a[2][2]=0;
    i2[1][1]=1;i2[1][2]=0;
    i2[2][1]=0;i2[2][2]=1;
    n--;
    while(n)
    {
        if(n&1) mult(i2, a);
        mult(a, a);
        n >>= 1;
    }
    g << i2[1][1]%MOD;


    return 0;
}