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