#include <iostream>
#include<fstream>
using namespace std;

const long long int mod = 666013;

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

void inmultire(unsigned long long int a[2][2], unsigned long long int b[2][2], unsigned long long int c[2][2])
{
    int aux[2][2];
    aux[0][0]=(a[0][0]*b[0][0]%mod + a[0][1]*b[1][0]%mod)%mod;
    aux[0][1]=(a[0][0]*b[0][1]%mod + a[0][1]*b[1][1]%mod)%mod;
    aux[1][0]=(a[1][0]*b[0][0]%mod + a[1][1]*b[1][0]%mod)%mod;
    aux[1][1]=(a[1][0]*b[0][1]%mod + a[1][1]*b[1][1]%mod)%mod;
    c[0][0]=aux[0][0];
    c[0][1]=aux[0][1];
    c[1][0]=aux[1][0];
    c[1][1]=aux[1][1];
}

void putere(unsigned long long int n[2][2],int p,unsigned long long int r[2][2])
{
    while(p != 0)
    {
    if(p % 2 == 1)
        inmultire(r,n,r);
    inmultire(n,n,n);
    p/=2;
    }
}

int main()
{
    unsigned long long int c[2][2] = {{0,1},{1,1}},r[2][2] = {{1,0},{0,1}},n;
    int s = 0;
    f>>n;
    putere(c,n-2,r);
    s = r[1][0] + r[1][1];
    g<<s % mod;
    return 0;
}