#include <fstream>
#define int long long
#define mod 1048576
#define nmax (int)(15e6+1)
using namespace std;
ifstream cin("12perm.in");
ofstream cout("12perm.out");
int dp[nmax],n;
signed main()
{
    dp[1]=1,dp[2]=2,dp[3]=6,dp[4]=12;
    cin>>n;
    for(int i=5;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-3]+2*(i-2);
        while(dp[i]>=mod)
            dp[i]-=mod;
    }
    cout<<dp[n];
    return 0;
}