#include <fstream>

using namespace std;
const int mask = (1 << 20) - 1;
const int Nmax = 15000005;

int F[Nmax];

int main()
{
    ifstream f ("12perm.in");
    ofstream g ("12perm.out");

    int N;
    f >> N;
    F[0] = 0;
    F[1] = F[2] = 1;

    if (N < 3) { g << N << endl; return 0; }

    int ans = 4;
    for (int n = 3; n <= N; n++) {
        F[n] = (F[n-1] + F[n-3] + 1) & mask;
        ans = (ans + 2*F[n]) & mask;
    }

    ans = (ans + 2*(mask + 1 - F[N-1])) & mask;
/*
    int ans = (2*F[N]) & mask;

    for (int i = 1; i < N/2; i++) {
        ans = (ans + 2*(F[N - 2*i - 1] + F[N - 2*i])) & mask;
    }

    if (N%2 == 1)
        ans = (ans + 2) & mask;
*/
    g << ans << endl;

    return 0;
}