#include <iostream>
#include <vector>
#include <map>
#include <math.h>
#include <fstream>

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfob.out");
map<int,int> fib;

long long fib1(long n,long long k)
{
    long long f1=1,f2=1,f3;
    for(long long i=1;i<n;i++)
    {
        f3 = (f2+f1) %k;
        f1 = f2%k;
        f2 = f3%k;
    }
    return f1;
}

long long fib2(long q, long long k)
{

    if(q<3) return 1;
    //cout<<q<<" ";
    if(fib[q]) return fib[q];

    char c;
    //cin>>c;
    long n = q/2;
    if(q%2)
    {
        long long l = fib2(n+1,k)%k;
        long long r = fib2(n,k)%k;
        r =  l*l+r*r;
        fib[q] = r%k;
        //cout<<q<<" "<<r<<endl;
        return r%k;
    }
    else
    {
        long long r = fib2(n,k)%k*(fib2(n+1,k)%k+fib2(n-1,k)%k);
        fib[q] = r%k;
        //cout<<q<<" "<<r<<endl;
        return r%k;
    }

}
int main()
{
    fib[0] = 0;
    fib[1] = fib[2] = 1;

    long n = 10000000000;
    long long k = 666013;
    fin>>n;
    //long r1 =fib1(n,k);
    long r2 = fib2(n,k);
//    if(r1!=r2) cout<<"alert";
    fout<<r2;
    //cout<<fib.size();


    return 0;
}