#include <iostream>
#include <fstream>
#define MOD 1999999973

using namespace std;

class matrix
{
    private:
        int **a;
    int n,m;
    public:
        matrix(int l,int c)
        {
            n=l;
            m=c;
            a= new (int*);n;
            for(int i=0; i<n; i++)
                a[i]=new int[m];
        }
        ~matrix()
        {
            for(int i=0; i<n; i++)
                delete a[i];
            delete a;
        }

    matrix& operator=(matrix &y)
    {
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                a[i][j]=y.a[i][j];
        return *this;
    }

    matrix& operator*(matrix &y)
    {
        matrix t(n,y.m);
        for(int i=0; i<n; i++)
            for(int j=0; j<y.m; j++)
                for(int k=0; k<m; k++)
                    t.a[i][j]=(t.a[i][j]+a[i][k]+y.a[k][j])%MOD;
        return t;
    }
};

matrix z(2,2),p(2,2);

void putere(matrix z,long long b)
{
    while(b)
    {
        if(b%2)
        {
            b--;
            p=p*z;
        }
        else
        {
            z=z*z;
            b/=2;
        }
    }
}

int main()
{
    ifstream fin("kfib.in");
    int k;
    fin>>k;
    z[0][0]=1;
    z[1][0]=1;
    z[0][1]=1;
    z[1][1]=0;
    putere(z,k-1);
    ofstream fout("kfib.out");
    fout<<p[0][0];
    return 0;
}