#include <fstream>
using namespace std;


const int mod=666013;


void hatvany(int n, long long a[2][2], long long b[2][2])
{
    if(n!=1)
        if(n%2==0){
            long long aux[2][2], aux2[2][2];
            aux[0][0]=aux2[0][0]=a[0][0];
            aux[0][1]=aux2[0][1]=a[0][1];
            aux[1][0]=aux2[1][0]=a[1][0];
            aux[1][1]=aux2[1][1]=a[1][1];

            a[0][0]=(aux[0][0]*aux2[0][0]+aux[0][1]*aux2[1][0])%mod;
            a[0][1]=(aux[0][0]*aux2[0][1]+aux[0][1]*aux2[1][1])%mod;
            a[1][0]=(aux[1][0]*aux2[0][0]+aux[1][1]*aux2[1][0])%mod;
            a[1][1]=(aux[1][0]*aux2[0][1]+aux[1][1]*aux2[1][1])%mod;
            hatvany(n/2, a, b);
        } else{
            long long aux[2][2], aux2[2][2];
            aux[0][0]=b[0][0];
            aux[0][1]=b[0][1];
            aux[1][0]=b[1][0];
            aux[1][1]=b[1][1];

            b[0][0]=(a[0][0]*aux[0][0]+a[0][1]*aux[1][0])%mod;
            b[0][1]=(a[0][0]*aux[0][1]+a[0][1]*aux[1][1])%mod;
            b[1][0]=(a[1][0]*aux[0][0]+a[1][1]*aux[1][0])%mod;
            b[1][1]=(a[1][0]*aux[0][1]+a[1][1]*aux[1][1])%mod;

            aux[0][0]=aux2[0][0]=a[0][0];
            aux[0][1]=aux2[0][1]=a[0][1];
            aux[1][0]=aux2[1][0]=a[1][0];
            aux[1][1]=aux2[1][1]=a[1][1];

            a[0][0]=(aux[0][0]*aux2[0][0]+aux[0][1]*aux2[1][0])%mod;
            a[0][1]=(aux[0][0]*aux2[0][1]+aux[0][1]*aux2[1][1])%mod;
            a[1][0]=(aux[1][0]*aux2[0][0]+aux[1][1]*aux2[1][0])%mod;
            a[1][1]=(aux[1][0]*aux2[0][1]+aux[1][1]*aux2[1][1])%mod;
            hatvany((n-1)/2, a, b);
        }
}


long long matyas(int k)
{
    long long a[2][2]={{0,1},{1,1}}, b[2][2]={{1,0},{0,1}};

    if (k == 0) return 0;
    else if (k == 1) return 1;
    hatvany(k-1, a, b);
    return (a[1][0]*b[0][1]+a[1][1]*b[1][1])%mod;
}


int main()
{
    /*ofstream fout("output.txt");

    long long a = 0, b = 1, c = 1;
    for (int i = 0; i < 100000000; ++i) {
        // F(i) == a

        long long f = matyas(i);

        if (a == f) {
            //fout << i << " ok\n";
        }
        else {
            fout << i << " " << a << " " << f << "\n";
        }

        a = b;
        b = c;
        c = (a + b) % mod;
    }

    fout << "a tobbi jo\n";*/

    ifstream fin("kfib.in");
    ofstream fout("kfib.out");

    int k;
    fin >> k;
    fout << matyas(k) << endl;
}