#include <bits/stdc++.h>
#define mod 666013
using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

struct mat
{
    long long m[3][3];
};

mat prod(mat a, mat b)
{
    mat c;
    c.m[1][1]=a.m[1][1]*b.m[1][1]%mod+a.m[1][2]*b.m[2][1]%mod;
    c.m[1][2]=a.m[1][1]*b.m[1][2]%mod+a.m[1][2]*b.m[2][2]%mod;
    c.m[2][1]=a.m[2][1]*b.m[1][1]%mod+a.m[2][2]*b.m[2][1]%mod;
    c.m[2][2]=a.m[2][1]*b.m[1][2]%mod+a.m[2][2]*b.m[2][2]%mod;
    return c;
}

mat po(mat a, long long k)
{
    if(k==1) return a;
    if(k%2==0)
        return po(prod(a,a),k/2);
    return prod(a,po(prod(a,a),k/2));
}

int main()
{
    int n;
    fin>>n;
    mat f;
    f.m[1][1]=0;
    f.m[1][2]=1;
    f.m[2][1]=1;
    f.m[2][2]=1;
    fout<<po(f,n).m[1][2];

    return 0;
}