#include <iostream>
#include <stdio.h>
using namespace std;
typedef long long llong;

const llong MOD = 1001234567LL;
const llong DIV2 = 500617284LL;

llong ctr[1111];
llong pc[11][1111];

int x;
int popcnt[1111];

llong perpop[21];

int main()
{
    freopen("intpairs.in", "r", stdin);
    freopen("intpairs.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int i,j;
    llong ans = 0;

    for (i=0;i<(1<<10);i++)
    {
        popcnt[i] = 0;
        int cp = i;
        while(cp > 0)
        {
            if (cp % 2 == 1)
                popcnt[i]++;
            cp /= 2;
        }
    }

    for (i=0;i<=10;i++)
    {
        pc[i][0] = 1LL;
    }
    pc[0][0] = 0LL;
    for (i=1;i<(1<<10);i++)
    {
        for (j=0;j<=10;j++)
        {
            pc[j][i] = (pc[j][i-1] * j) % MOD;
        }
    }

    cin>>x;

    for (i=0;i<(1<<10);i++)
    {
        bool has0 = i % 2 == 1;
        int cnt = popcnt[i];

        for (j=1;j<=x;j++)
        {
            if (!has0)
            {
                ctr[i] += pc[cnt][j];
                if (ctr[i] >= MOD)
                    ctr[i] -= MOD;
            }
            else
            {
                ctr[i] += (cnt - 1) * pc[cnt][j-1];
                ctr[i] %= MOD;
            }
        }

        perpop[cnt] += ctr[i];
    }
    ctr[0] = 0;
    ctr[1] = 0;

    for (i=(1<<10)-1;i>=0;i--)
    {
        for (j=0;j<(1<<10);j++)
        {
            if ( (i | j) != i )
                continue;
            if (i == j)
                continue;

            if (popcnt[j] % 2 == popcnt[i] % 2)
            {
                ctr[i] += ctr[j];
                if (ctr[i] >= MOD)
                    ctr[i] -= MOD;
            }
            else
            {
                ctr[i] -= ctr[j];
                if (ctr[i] < 0)
                    ctr[i] += MOD;
            }
        }
    }

    llong base = 0;
    base = 0;
    for (i=1;i<=x;i++)
    {
        base += 9LL * pc[10][i-1];
        base %= MOD;
    }

    ans = base;
    llong ls = (base - 1LL + MOD) % MOD;
    ans *= ls;
    ans %= MOD;
    ans *= DIV2;
    ans %= MOD;

    for (i=0;i<(1<<10);i++)
    {
        for (j=i+1;j<(1<<10);j++)
        {
            if ( (i & j) != 0 )
                continue;

            ans -= (ctr[i] * ctr[j]) % MOD;
            if (ans < 0)
                ans += MOD;
        }
    }

    cout<<ans<<endl;

    return 0;
}