#include <fstream>
#include <vector>
#define NMAX 666013
using namespace std;

void multiplication(long long rezult[][2],long long term1[][2],long long term2[][2]){

    rezult[0][0] = (((term1[0][0] * term2[0][0]) % NMAX + (term1[0][1] * term2[1][0]) % NMAX) % NMAX);
    rezult[0][1] = (((term1[0][0] * term2[0][1]) % NMAX + (term1[0][1] * term2[1][1]) % NMAX) % NMAX);
    rezult[1][0] = (((term1[1][0] * term2[0][0]) % NMAX + (term1[1][1] * term2[1][0]) % NMAX) % NMAX);
    rezult[1][1] = (((term1[1][0] * term2[0][1]) % NMAX + (term1[1][1] * term2[1][1]) % NMAX) % NMAX);

}

void power(long long a[][2], long long p){

    if(p==0){
        a[0][0] = a[1][1] = 1;
        a[1][0] = a[0][1] = 0;
        return;
    }

    if(p==1)
        return;

    long long t1[2][2],rez[2][2],rez2[2][2];
    t1[0][0] = a[0][0]; t1[1][0] = a[1][0]; t1[0][1] = a[0][1]; t1[1][1] = a[1][1];

    power(t1,p/2);
    multiplication(rez,t1,t1);

    if(p&1){
        multiplication(rez2,rez,a);
        a[0][0] = rez2[0][0]; a[1][0] = rez2[1][0]; a[0][1] = rez2[0][1]; a[1][1] = rez2[1][1];
   }
   else{
       a[0][0] = rez[0][0]; a[1][0] = rez[1][0]; a[0][1] = rez[0][1]; a[1][1] = rez[1][1];
   }

}

int main()
{
    long long n,a[2][2];
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    f >> n;
    a[0][0] = a[1][0] = a[0][1] = 1;
    a[1][1] = 0;
    power(a,n-1);
    if(n!=0)
        g << a[0][0];
    else g << 0;
    return 0;
}