/*#include <fstream>
 
using namespace std;
 
ifstream in ("kfib.in");
ofstream out ("kfib.out");
const int R=666013;
 
long long a[2][2],b[2][2],p[2][2];
 
void produs()
{
    int aux[2][2];
    aux[0][0]=(a[0][0]*a[0][0]+a[0][1]*a[1][0])%R;
    aux[0][1]=(a[0][0]*a[0][1]+a[0][1]*a[1][0])%R;
    aux[1][0]=(a[1][0]*a[0][0]+a[1][1]*a[1][0])%R;
    aux[1][1]=(a[1][0]*a[0][1]+a[1][1]*a[1][1])%R;
    for(int i=0;i<=1;i++)
        for(int j=0;j<=1;j++)
            a[i][j]=aux[i][j];
 
}
void putere(long long n)
{
    if(n==1)
        return;
    if(n%2==1)
    {
        produs();
    }
 
    putere(n/2);
    return;
}
int main()
{
    int n;
    in>>n;
    a[0][0]=1;
    a[0][1]=1;
    a[1][0]=1;
    putere(n-1);
    out<<a[0][0];
 
    return 0;
}*/
 
 
#include <fstream>
using namespace std;
 
const int mod = 666013;
 
long long prod[2][2];
 
void produs(long long a[2][2], long long b[2][2])
{
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            prod[i][j] = (a[i][0]*b[0][j] + a[i][1]*b[1][j]) % mod;
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            a[i][j] = prod[i][j];
}
 
int main()
{
    ifstream in("kfib.in");
    ofstream out("kfib.out");
    int n;
    in >> n;
    long long a[2][2] = {{1,0},{0,1}};
    long long b[2][2] = {{0,1},{1,1}};
    for (int i = 0; i < 30; ++i) {
        if (1<<i & n)
            produs(a,b);
        produs(b,b);
    }
    out << a[0][1];
    return 0;
}