#include <fstream>
using namespace std;

ifstream fin("12perm.in");
ofstream fout("12perm.out");

const int MOD = 1048576;
using LL = long long;
int N;
LL rez;

int RidicareLaPutere( int a, int p );

int main()
{
    fin >> N;

    rez = ( N - 2 )*4;

    rez = ( (1LL*rez) + (1LL*RidicareLaPutere(2, N - 2)) ) % MOD;

    fout << rez << '\n';

    fin.close();
    fout.close();
    return 0;
}

int RidicareLaPutere( int a, int p )
{
    int rez = 1;

    while ( p > 0 )
    {
        if ( p % 2 )
        {
            rez = ( (1LL*rez) * (1LL*a) ) % MOD;
            p--;
        }

        a = ( (1LL*a) * (1LL*a) ) % MOD;
        p /= 2;
    }

    return rez;
}