#include <vector> 
#include <list> 
#include <map> 
#include <set> 
#include <deque> 
#include <queue> 
#include <stack> 
#include <bitset> 
#include <algorithm> 
#include <functional> 
#include <numeric> 
#include <utility> 
#include <sstream> 
#include <iostream> 
#include <iomanip> 
#include <cstdio> 
#include <cmath> 
#include <cstdlib> 
#include <cctype> 
#include <string> 
#include <cstring> 
#include <ctime> 

using namespace std;

#define _int64 long long
#define mo 123456789

vector<int> aa;
map<int,int> mp;
int a[20000];
int d[11000][110];
int dd[110][11000];

int lowbit(int x)
{
  return ((x^(x-1))&x);
}

void add1(int ind,int x,int v)
{
  int i;
  for (i=x;i<11000;i+=lowbit(i))
  {
    dd[ind][i]+=v;
    if (dd[ind][i]>=mo) dd[ind][i]-=mo;
  }
}

int get1(int ind,int x)
{
  int ret,i;
  ret=0;
  for (i=x;i>0;i-=lowbit(i))
  {
    ret+=dd[ind][i];
    if (ret>=mo) ret-=mo;
  }
  return ret;
}

int main()
{
  int i,j,n,m,ans,tmp;
  while (scanf("%d%d",&n,&m)!=EOF)
  {
    aa.clear();
    for (i=0;i<n;i++)
    {
      scanf("%d",&a[i]);
      aa.push_back(a[i]);
    }
    sort(aa.begin(),aa.end());
    aa.erase(unique(aa.begin(),aa.end()),aa.end());
    mp.clear();
    for (i=0;i<aa.size();i++)
      mp[aa[i]]=i+2;
    for (i=0;i<n;i++)
      a[i]=mp[a[i]];
    memset(dd,0,sizeof(dd));
    memset(d,0,sizeof(d));
    d[0][0]=1;
    add1(0,1,1);
    for (i=0;i<n;i++)
    {
      for (j=1;j<=m;j++)
      {
        tmp=get1(j-1,a[i]-1);
        add1(j,a[i],tmp);
      }
    }
    ans=get1(m,10999);
    cout<<ans<<endl;
  }
  
}