#include <bits/stdc++.h>
#define ll unsigned long long int
#define MOD 666013
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define LONG_MAX 1LL << 63
#define LONG_MIN -1LL << 63
#define INT_MAX 1<<31 -1
#define INT_MIN -1<<31 +1

using namespace std;
string fis="kfib";
ifstream fin(fis+".in");
ofstream fout(fis+".out");
int M[3][3] = { {0, 0, 0}, {0, 1, 1}, {0, 1, 0} };
int n;
void copyM(int A[][3] , int B[][3])
{
    for(int i = 1; i <= 2; ++i)
    {
        for(int j = 1; j <= 2 ; ++j)
            A[i][j] = B[i][j];
    }
}
void multiply(int A[][3],int B[][3])
{
    int C[3][3];
    for(int i = 1; i <= 2; ++i)
    {
        for(int j = 1 ; j<= 2; ++j)
        {
            C[i][j] = 0;
            for(int k = 1 ; k <= 2; ++k)
                C[i][j] += (1ll * A[i][k] * B[k][j]) % MOD;
            C[i][j] %= MOD;
        }
    }
    copyM(A , C);
}
int expMat(int A[][3])
{
    int R[3][3];
    copyM(R , M);
    while(n)
    {
        if(n & 1)multiply(R , M);
        multiply(M , M);
        n >>= 1;
    }
    return R[1][1];
}
int main()
{
    FAST
    fin >> n;
    if(n == 0)fout << 0;
    else if(n == 1)fout << 1;
    else
    {
        n -= 2;
        fout << expMat(M);
    }
}