1 #include<cstdio>

 2 #include<cstring>

 3 #include<algorithm>

 4 #define mod 123456789

 5 typedef long long ll;

 6 using namespace std;

 7 #define N 10005

 8

 9 ll a[N],b[N];

10 ll dp[N][105];

11 int n,m,len;

12

13 int lowbit(int x){

14     return x&(-x);

15 }

16

17 void add(int i,int j,ll val){

18     while(i<=len){

19         dp[i][j]=(dp[i][j]+val)%mod;

20         i+=lowbit(i);

21     }

22 }

23

24 ll query(int i,int j){

25     ll res=0;

26     while(i){

27         res=(res+dp[i][j])%mod;

28         i-=lowbit(i);

29     }

30     return res;

31 }

32

33

34

35 int main(){

36     while(~scanf("%d%d",&n,&m)){

37         for(int i=1;i<=n;i++){

38             scanf("%lld",&a[i]);

39             b[i]=a[i];

40         }

41         memset(dp,0,sizeof(dp));

42         sort(b+1,b+n+1);

43         len=unique(b+1,b+n+1)-b-1;

44         for(int i=1;i<=n;i++){

45             int pos=lower_bound(b+1,b+len+1,a[i])-b;

46             add(pos,1,1);

47             for(int j=2;j<=m;j++){

48                 int sum=query(pos-1,j-1);

49                 add(pos,j,sum);

50             }

51         }

52         printf("%lld\n",query(len,m));

53     }

54     return 0;

55 }