#include <iostream>
#include <fstream>
#define ll long long
#define mod 666013
using namespace std;
ll n;
struct Matrix
    {
        ll x,y,z,t;
    };
Matrix attrib(ll a, ll b, ll c, ll d)
        {
            Matrix A;
            A.x=a;
            A.y=b;
            A.z=c;
            A.t=d;
            return A;
        }
Matrix product(Matrix A, Matrix B)
              {return attrib((A.x * B.x + A.y*B.z) % mod, (A.x * B.y + A.y*B.t) % mod, (A.z*B.x + A.t*B.z) % mod, (A.z*B.y+A.t*B.t) % mod); }

Matrix power (Matrix A, int pow)
           {
               if (pow==1) return A;
               Matrix half=power(A, pow/2);
               if (pow % 2 == 0) return product (half,half);
               return product (product(half,half), A);
           }

int main()
{
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    f>>n;
    g<< power (attrib (0,1,1,1), n).z;

    return 0;
}