#include<fstream>
using namespace std;
#define Mod 666013
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long n;
struct matrix
{long long a11,a12,a21,a22;
} Z,M;
matrix produs(matrix A, matrix B)
{matrix C;
C.a11=((A.a11*B.a11)%Mod+(A.a12*B.a21)%Mod)%Mod;
C.a12=((A.a11*B.a12)%Mod+(A.a12*B.a22)%Mod)%Mod;
C.a21=((A.a21*B.a11)%Mod+(A.a22*B.a21)%Mod)%Mod;
C.a22=((A.a21*B.a12)%Mod+(A.a22*B.a22)%Mod)%Mod;
return C;
}
matrix power(long long k)
{if (k==1) return Z;
if (k%2) return produs(Z,power(k-1));
else return produs(power(k>>1),power(k>>1));
}
int main()
{
fin>>n;
Z.a12=Z.a21=Z.a22=1;
M=power(n-1);
fout<<M.a22<<'\n';
return 0;
}