/*4991    655MS    9664K    1701 B    G++    2014300227*/
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5;
typedef long long ll;
const ll mod=123456789;
int n,m;
ll sum[N],dp[102][N];
int lowbit(int x)
{
    return x&(-x);
}
void update(int x,ll num)
{
    while(x<=n)
    {
        sum[x]+=num;
        sum[x]%=mod;
        x+=lowbit(x);
    }
}
ll query(int x)
{
    ll s=0;
    while(x>0)
    {
        s+=sum[x];
        s%=mod;
        x-=lowbit(x);
    }
    return s;
}
struct node
{
    int num,pos,c,d;
};
node po[N];
int cmp1(node x,node y)
{
    if(x.num==y.num)return x.pos<y.pos;
    return x.num<y.num;
}
int cmp2(node x,node y)
{
    return x.pos<y.pos;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)scanf("%d",&po[i].num),po[i].pos=i;
        sort(po+1,po+n+1,cmp1);
        po[0].num=-1;
        for(int i=1;i<=n;i++)
        {
            if(po[i].num==po[i-1].num)
            {
                po[i].c=po[i-1].c;
            }
            else po[i].c=i;//po[i].c表示第一个跟po[i].num相同的数的位置;
            po[i].d=i;//表示po[i]插入时的位置;
        }
        sort(po+1,po+n+1,cmp2);
        for(int i=1;i<=n;i++)
        {
            dp[1][i]=1;
            update(po[i].d,1);
        }
        for(int i=2;i<=m;i++)
        {
            memset(sum,0,sizeof(sum));
            for(int j=1;j<=n;j++)
            {
                if(po[j].c>1)
                dp[i][j]=query(po[j].c-1);//转移方程;
                else dp[i][j]=0;
                update(po[j].d,dp[i-1][j]);//把dp[i-1][j]更新上去;
            }
        }
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            ans+=dp[m][i];
            ans%=mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}