#include<bits/stdc++.h>

using namespace std;

const long long mo = 1001234567;
const int maxi = 1e3+10;
#define pb push_back
int n;
int a[maxi];
long long dp[1<<10][maxi];
long long ans;
int x;

void read_data()
{
    freopen("intpairs.in", "r", stdin);

    cin>>x;

    dp[0][0] = 1;

    for (int i = 1; i<=x; i++)
    {
        for (int mask =2; mask<(1<<10); mask++)
        {
            for (int val = mask;val>0;val -= val&-val){
                int z = val & - val;
                if ((mask&z) && ((mask^z)!=1)){
                    dp[mask][i]+=dp[mask^z][i-1];
                }
            }

            dp[mask][i]+=dp[mask][i-1]*__builtin_popcount(mask);
            while(dp[mask][i] >=mo) dp[mask][i]-=mo;
        }

        dp[0][i] = 1;
    }

    for (int mask = 2; mask<(1<<10); mask++)
        for(int mask1 = mask; mask1<(1<<10);mask1++)
        if (mask1!= mask && (mask1 & mask))
    {
        ans+=dp[mask1][x]*dp[mask][x];
        if (ans>7e18) ans%=mo;
    } else
    if (mask1 == mask){
       ans+=dp[mask][x]*(dp[mask][x]-1)%mo* 500617284%mo;
       ans%=mo;
    }
    ans%=mo;

    fclose(stdin);
}

void print_data()
{
     freopen("intpairs.out", "w",stdout);

      cout<<ans<<endl;
     fclose(stdout);
}

int main()
{
    read_data();

    print_data();
}