// Rain Dreamer MODEL
// INFO
// Comment - 

#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
#include <bitset>
#include <queue>
#include <map>
#include <set>

using namespace std;

// Self Template Code BGEIN

#define sz(x) ((int)((x).size()))
#define out(x) printf(#x" %d\n", x)
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repf(i,a,b) for (int i = (a); i <= (b); ++i)
#define repd(i,a,b) for (int i = (a); i >= (b); --i)
#define repcase int t, Case = 1; for (scanf ("%d", &t); t; --t)
#define repeach(i,x) for (__typeof((x).begin()) i = (x).begin(); i != (x).end(); ++i)

typedef long long int64;
typedef pair<int, int> pii;

int sgn(double x) { return (x > 1e-8) - (x < -1e-8); }
int count_bit(int x) { return x == 0? 0 : count_bit(x >> 1) + (x & 1); }

template<class T> inline void ckmin(T &a, const T b) { if (b < a) a = b; }
template<class T> inline void ckmax(T &a, const T b) { if (b > a) a = b; }

// Self Template Code END

const int MOD = 123456789;
const int MAXN = 10000 + 10;

struct binary_indexed_tree {
    #define lowbit(x) ((x) & (-(x)))
    int a[MAXN], n;

    void clear(int _n) {
        n = _n;
        memset (a, 0, sizeof(int) * (n + 1));
    }
    void update(int x, int y) {
        for (; x <= n; x += lowbit(x)) {
            a[x] += y;
            if (a[x] >= MOD) a[x] -= MOD;
        }
    }
    int getsum(int x) {
        int ret = 0;
        for (; x; x -= lowbit(x)) {
            ret += a[x];
            if (ret >= MOD) ret -= MOD;
        }
        return ret;
    }
};

binary_indexed_tree bit[102];
int b[MAXN], un;
int a[MAXN], n, m;

int get_id(int x) {
    return lower_bound(b, b + un, x) - b + 1;
}

int main() {
    while (scanf ("%d%d", &n, &m) != EOF) {
        rep (i, n) {
            scanf ("%d", &a[i]);
            b[i] = a[i];
        }
        sort (b, b + n);
        un = unique(b, b + n) - b;

        rep (i, m) {
            bit[i].clear(un);
        }
        rep (i, n) {
            int num = get_id(a[i]);
            repd (j, m - 1, 1) {
                bit[j].update(num, bit[j - 1].getsum(num - 1));
            }
            bit[0].update(num, 1);
        }
        printf ("%d\n", bit[m - 1].getsum(un));
    }
    return 0;
}