#include <bits/stdc++.h>

using namespace std;

const int k_Mod = 1001234567;
const int k_X = 1000 + 3;

long long cnt[(1 << 10)];
long long power[11][k_X];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    freopen("intpairs.in", "r", stdin);
    freopen("intpairs.out", "w", stdout);

    int x;
    cin >> x;

    for(int i = 1; i <= 10; ++i){
        power[i][0] = 1;
        for(int j = 1; j < k_X; ++j)
            power[i][j] = power[i][j - 1] * i % k_Mod;
    }

    for(int i = 1; i < (1 << 10); ++i){
        cnt[i] = 0;

        int count_digits = __builtin_popcount(i);

        if(i & (1 << 0)){
            for(int j = 0; j < x; ++j){
                cnt[i] += (count_digits - 1) * power[count_digits][x - j - 1] % k_Mod;
                if(cnt[i] >= k_Mod)
                    cnt[i] -= k_Mod;
            }
        }
        else{
            for(int j = 0; j < x; ++j){
                cnt[i] += power[count_digits][x - j] % k_Mod;
                if(cnt[i] >= k_Mod)
                    cnt[i] -= k_Mod;
            }
        }
    }

    for(int i = 1; i < (1 << 10); ++i){
        for(int j = 1; j < i; ++j){
            if((i | j) == i){
                cnt[i] += k_Mod;
                cnt[i] -= cnt[j];
                if(cnt[i] >= k_Mod)
                    cnt[i] -= k_Mod;
            }
        }
    }

    long long answer = 0;
    for(int i = 1; i < (1 << 10); ++i){
        answer += (cnt[i] * (cnt[i] - 1) / 2) % k_Mod;
        if(answer >= k_Mod)
            answer -= k_Mod;

        for(int j = i + 1; j < (1 << 10); ++j){
            if(i & j){
                answer += (cnt[i] * cnt[j]) % k_Mod;
                if(answer >= k_Mod)
                    answer -= k_Mod;
            }
        }
    }


    cout << answer << "\n";
}