#include <iostream>

using namespace std;

long long dp[1000001];

int main()
{
    int n, i;
    ifstream cin("12perm.in");
    ofstream cout("12perm.out");
    cin >> n;
    dp[0] = 1;
    for(i = 1; i <= n; i++){
        if(i - 3 >= 0)
            dp[i] += dp[i - 3];
        dp[i] += dp[i - 1];
        if(i >= 4)
            dp[i]++;
        dp[i] %= 1048576;
    }
    cout << ((n - 2) * 2 + dp[n] * 2) % 1048576 ;
    return 0;
}