#include <bits/stdc++.h>
#define MOD 666013
using namespace std;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
struct matrix
{
    int v[4][4];
    int n, m;
};
int K;
matrix prim, a, p;
void inmultire(matrix& a, matrix b)
{
    matrix c;
    c.n = a.n, c.m = b.m;
    for(int i=0; i<c.n; i++)
        for(int j=0; j<c.m; j++)
            c.v[i][j] = 0;
    for(int i=0; i<a.n; i++)
        for(int j=0; j<b.m; j++)
            for(int k=0; k<a.m; k++)
            {
                c.v[i][j]+=(1LL*a.v[i][k]*b.v[k][j])%MOD;
                c.v[i][j]%=MOD;
            }
    a = c;
}
int main()
{
    fin >> K;
    K--;
    a.n = a.m = 2;
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            a.v[i][j]= 1;
    a.v[1][1] = 0;
    prim.n = 2, prim.m = 1;
    prim.v[0][0] = 1;
    prim.v[1][0] = 0;
    p.n = p.m = 2;
    p.v[0][0] = p.v[1][1] = 1;
    p.v[0][1] = p.v[1][0] = 0;
    while(K)
    {
        if(K%2==1)
            inmultire(p, a);
        inmultire(a, a);
        K/=2;
    }
    inmultire(p, prim);
    fout << p.v[0][0];

    return 0;
}