#include <fstream>
#include <vector>
#include <queue>
#define M 666013

using namespace std;

ifstream cin("kfib.in");
ofstream cout("kfib.out");

int n,p;
int a[3][3],b[3][3],c[3][3];

void mult(int A[][3],int B[][3],int C[][3], int n)
{
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=2;j++)
        {
            C[i][j]=((A[i][1]*B[j][1])%M+(A[i][2]*B[j][2])%M)%M;
        }
    }
}

void egal(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 fib(int A[][3],int B[][3],int C[][3],int p)
{
    while (p>0)
    {
        if(!p%2)
        {
            mult(A,A,B,2);
            egal(A,B);
            p=p/2;
        }
        else
        {
            mult(C,A,B,2);
            egal(C,B);
            p--;
        }
    }
    mult(A,C,B,2);
}



int main()
{
    cin >> n;
    c[1][1]=1;
    c[2][2]=1;
    a[1][2]=1;
    a[2][1]=1;
    a[2][2]=1;
    fib(a,b,c,n-1);
    cout << b[2][2];
}