#include <fstream>
#include<bits/stdc++.h>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
#define int long long
typedef vector<vector<int>> matrix;
const int MOD=666013;
matrix inmultire2x2(matrix A,matrix B)
{
    matrix C;
    C.assign(2,vector<int>(2,0));
    for(int i=0; i<2; i++)
    {
        for(int j=0; j<2; j++)
        {
            for(int k=0;k<2;k++)
            {
                C[i][j]=(C[i][j]+1LL*A[i][k]*B[k][j]%MOD)%MOD;
            }
        }
    }
    return C;
}
matrix exp(matrix A,int n)
{
    matrix P;
    P.assign(2,vector<int>(2,0));
    for(int i=0;i<2;i++)
    P[i][i]=1;
    while(n)
    {
        if(n%2)P=inmultire2x2(P,A);
        A=inmultire2x2(A,A);
        n=n/2;
    }
    return P;
}
int32_t main()
{
    matrix recurrent_matrix={{0,1},{1,1}};
    int f0=0;
    int f1=1;
    int n;
    fin>>n;
    recurrent_matrix=exp(recurrent_matrix,n-1);
    int fn=0;
    fn=(f0*recurrent_matrix[0][1]+f1*recurrent_matrix[1][1])%MOD;
    fout<<fn;
    return 0;
}