#include <iostream>
#include <fstream>
#define NMAX 2000
#define mod (1<<20)
using namespace std;

long long n, e1, e2, e3, e4;
int main ()
{
    // T;
    ifstream cin ("12perm.in");
    ofstream cout ("12perm.out");
    cin >> n;
   
  e1 = 1;
    e2 = 2;
    e3 = 6;
    e4 = 12;
    if (n == 1)
        cout << e1;
    if (n == 2)
        cout << e2;
    if (n == 3)
        cout << e3;
    if (n == 4)
        cout << e4;
    for (int i = 5; i <= n; i++)
    {
        e1 = e2;
        e2 = e3;
        e3 = e4;
        e4 = (e1 + e3 + 2 * (i - 2)) &( mod - 1);
    }
    cout << e4;
    return 0;
}