#include <fstream>
#define MOD 666013
 
using namespace std;
 
ifstream fin("kfib.in");
ofstream fout("kfib.out");
 
long long M[3][3], n, cn, Sol[3][3];
 
void Imat(long long A[3][3], long long B[3][3], long long (&S)[3][3])
{
    long long P[3][3];
    P[1][1] = A[1][1]*B[1][1] + A[1][2]*B[2][1];
    P[1][2] = A[1][1]*B[1][2] + A[1][2]*B[2][2];
    P[2][1] = A[2][1]*B[1][1] + A[2][2]*B[2][1];
    P[2][2] = A[2][1]*B[1][2] + A[2][2]*B[2][2];
    S[1][1]=P[1][1]%MOD;
    S[1][2]=P[1][2]%MOD;
    S[2][1]=P[2][1]%MOD;
    S[2][2]=P[2][2]%MOD;
}
 
int main()
{
    fin>>n;
    M[1][1]=0;
    M[1][2]=1;
    M[2][1]=1;
    M[2][2]=1;
    if (n==1 || n==2)
        fout<<1;
    else
    {
        n-=2;
        cn=n;
        while (cn>0)
        {
            if (cn%2==1)
            {
                if (Sol[2][2]!=0)
                {
                    Imat(Sol, M, Sol);
                }
                else
                {
                    Sol[1][1]=M[1][1];
                    Sol[1][2]=M[1][2];
                    Sol[2][1]=M[2][1];
                    Sol[2][2]=M[2][2];
                }
            }
            cn /= 2;
            Imat(M, M, M);
        }
    }
    fout<<(Sol[2][1]+Sol[2][2])%MOD;
    return 0;
}