/// Moca Andrei - 100p
#include <fstream>
using namespace std;
const int mod = 301104;
long long x = 3, y = 5, z = 8, ax, ay;
int n;
int main()
{
    ifstream fin("bilean.in");
    fin >> n;
    fin.close();

    for (int i{4}; i <= n; ++i)
    {
        ax = x;
        ay = y;
        x = y;
        y = z;
        z = ax + ay;
        if (x > mod)
            x -= mod, y -= mod, z -= mod;
        else
            if (y > mod)
            	y -= mod, z -= mod;
        else
            if (z > mod)
            	z -= mod;
    }

    ofstream fout("bilean.out");
    if (n == 2)
        fout << 3;
    else
        if (n == 3)
            fout << 5;
    else
        fout << z;
    fout.close();
}