#include <fstream>
#define w 666013
#define ll long long
using namespace std;
int n;
ll a,b,c,d;
void exp_mat(ll &a,ll &b,ll &c,ll &d,ll n)
{
    ll x,y,z,t;
    if (n==1)
    {
        a=0; b=1; c=1; d=1;
    }
    else
    {
        exp_mat(x,y,z,t,n/2);
        a=(x*x+y*z)%w;
        b=(x*y+y*t)%w;
        c=(x*z+z*t)%w;
        d=(y*z+t*t)%w;
        if (n%2)
        {
            x=a; a=b;
            b=(x+b)%w;
            x=c; c=d;
            d=(x+d)%w;
        }
    }
}
int main()
{
    ifstream fin ("kfib.in");
    ofstream fout ("kfib.out");
    fin>>n;
    exp_mat(a,b,c,d,n-1);
    fout<<d;
    fin.close();
    fout.close();
    return 0;
}