#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef __int64 LL;
const int MAXN = 10002;
const LL mod = 123456789;
LL sum[102][MAXN];
int n, m, nm[MAXN];
int low_bit(int x)
{
return x&(-x);
}
void add(int x, LL v, int c)
{
while (x <= n)
{
sum[c][x] = (sum[c][x] + v)%mod;
x += low_bit(x);
}
}
LL get_sum(int x, int c)
{
LL res = 0LL;
while (x )
{
res += sum[c][x];
res %= mod;
x -= low_bit(x);
}
return res;
}
struct _node
{
int d, idx, c;
bool operator < (const _node & a) const
{
return d < a.d;
}
}da[MAXN];
LL dp[105];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
while (scanf("%d%d", &n, &m)!=EOF)
{
for (int i = 1; i<= n; ++i)
scanf("%d", &da[i].d), da[i].idx = i;;
sort(da+1, da+n+1);
da[0].d = -1; da[0].c = 1;
for (int i = 1; i<= n; ++i)
{
if (da[i].d == da[i-1].d)
da[i].c = da[i-1].c;
else
da[i].c = da[i-1].c+1;
}
for (int i = 1; i<=n; ++i)
{
nm[da[i].idx] = da[i].c;
}
LL res = 0;
memset(sum, 0, sizeof sum);
add(1, 1, 0); // 初始化要注意
for (int i = 1; i<= n; ++i)
{
for (int j = m; j>0; --j)
{
LL kk = get_sum(nm[i]-1, j-1);
add(nm[i], kk, j);
}
res += get_sum(nm[i]-1, m-1);
res %= mod;
}
printf("%I64d\n", res);
}
return 0;
}