#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <cassert>
#include <complex>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define ACCU accumulate
#define TWO(x) (1<<(x))
#define TWOL(x) (1ll<<(x))
#define clr(a) memset(a,0,sizeof(a))
#define POSIN(x,y) (0<=(x)&&(x)<n&&0<=(y)&&(y)<m)
#define PRINTC(x) cout<<"Case #"<<++__<<": "<<x<<endl 
#define POP(x) (__builtin_popcount(x))
#define POPL(x) (__builtin_popcountll(x))
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long ll;
typedef long double LD;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<ll> VL;
typedef vector<PII> VPII;
typedef complex<double> CD;
const int inf=0x20202020;
const ll mod=123456789;
const double eps=1e-9;
const double pi=3.1415926535897932384626;
const int DX[]={1,0,-1,0},DY[]={0,1,0,-1};
ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

int n,m,a[10100];
VI vec;
ll c[110][10100];
int dp[10100][110];
void modify(ll *c,int x,int s) { for (;x<=n;x+=x&-x) c[x]+=s;}
ll query(ll *c,int x) { ll s=0; for (;x;x-=x&-x) s+=c[x]; return s;}
int main() {
    while (scanf("%d%d",&n,&m)!=EOF) {
        vec.clear();
        rep(i,0,n) scanf("%d",a+i),vec.pb(a[i]);
        if (m>n) { puts("0"); continue;}
        sort(all(vec));
        rep(i,0,n) a[i]=lower_bound(all(vec),a[i])-vec.begin()+1;
        rep(i,1,n+1) rep(j,1,m+1) c[j][i]=0;
        ll ans=0;
        rep(i,0,n) {
            dp[i][1]=1;
            rep(j,2,m+1) dp[i][j]=query(c[j-1],a[i]-1)%mod;
            rep(j,1,m) modify(c[j],a[i],dp[i][j]);
            ans+=dp[i][m];
        }
        printf("%I64d\n",ans%mod);
    }
}