#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma pack(1)
using namespace std;
using namespace __gnu_pbds;
#define TASK "test"
#define int unsigned int
const int MOD=1000000000;
template<class Node_CItr,class Node_Itr,class Cmp_Fn,class _Alloc>
struct my_update_policy
{
virtual Node_CItr node_begin() const=0;
virtual Node_CItr node_end() const=0;
typedef int metadata_type;
int prefix_sum(int x)
{
int ans=0;
auto it=node_begin();
while(it!=node_end())
{
auto l=it.get_l_child();
auto r=it.get_r_child();
if(Cmp_Fn()(x,(*it)->first))
{
it=l;
}
else
{
ans+=(*it)->second;
if(l!=node_end()) ans+=l.get_metadata();
ans%=MOD;
it=r;
}
}
return ans;
}
void operator()(Node_Itr it, Node_CItr end_it)
{
auto l=it.get_l_child();
auto r=it.get_r_child();
int left=0,right=0;
if(l!=end_it) left=l.get_metadata();
if(r!=end_it) right=r.get_metadata();
const_cast<int&>(it.get_metadata())=(left+right+(*it)->second)%MOD;
}
};
tree<int,int,less<int>,rb_tree_tag,my_update_policy> me;
main()
{
#ifndef ONLINE_JUDGE
freopen(TASK".in","r",stdin);
freopen(TASK".out","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int n,k;
cin>>n>>k;
vector<int> a(n);
for(auto &it:a) cin>>it;
vector<int> inv(n,1);
for(int i=1;i<k;i++)
{
me.clear();
vector<int> t(n);
int sum=0;
for(int i=0;i<n;i++)
{
t[i]=sum-me.prefix_sum(a[i])+MOD;
me.insert({a[i],inv[i]});
sum+=inv[i];
sum%=MOD;
t[i]%=MOD;
}
swap(t,inv);
}
cout<<accumulate(inv.begin(),inv.end(),0ll)%MOD<<endl;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlIDxleHQvcGJfZHMvYXNzb2NfY29udGFpbmVyLmhwcD4KI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+CiNwcmFnbWEgcGFjaygxKQoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdXNpbmcgbmFtZXNwYWNlIF9fZ251X3BiZHM7CgojZGVmaW5lIFRBU0sgInRlc3QiCiNkZWZpbmUgaW50IHVuc2lnbmVkIGludApjb25zdCBpbnQgTU9EPTEwMDAwMDAwMDA7Cgp0ZW1wbGF0ZTxjbGFzcyBOb2RlX0NJdHIsY2xhc3MgTm9kZV9JdHIsY2xhc3MgQ21wX0ZuLGNsYXNzIF9BbGxvYz4Kc3RydWN0IG15X3VwZGF0ZV9wb2xpY3kKewogICAgdmlydHVhbCBOb2RlX0NJdHIgbm9kZV9iZWdpbigpIGNvbnN0PTA7CiAgICB2aXJ0dWFsIE5vZGVfQ0l0ciBub2RlX2VuZCgpIGNvbnN0PTA7CiAgICB0eXBlZGVmIGludCBtZXRhZGF0YV90eXBlOwoKICAgIGludCBwcmVmaXhfc3VtKGludCB4KQogICAgewogICAgICAgIGludCBhbnM9MDsKICAgICAgICBhdXRvIGl0PW5vZGVfYmVnaW4oKTsKICAgICAgICB3aGlsZShpdCE9bm9kZV9lbmQoKSkKICAgICAgICB7CiAgICAgICAgICAgIGF1dG8gbD1pdC5nZXRfbF9jaGlsZCgpOwogICAgICAgICAgICBhdXRvIHI9aXQuZ2V0X3JfY2hpbGQoKTsKICAgICAgICAgICAgaWYoQ21wX0ZuKCkoeCwoKml0KS0+Zmlyc3QpKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpdD1sOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgYW5zKz0oKml0KS0+c2Vjb25kOwogICAgICAgICAgICAgICAgaWYobCE9bm9kZV9lbmQoKSkgYW5zKz1sLmdldF9tZXRhZGF0YSgpOwogICAgICAgICAgICAgICAgYW5zJT1NT0Q7CiAgICAgICAgICAgICAgICBpdD1yOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHJldHVybiBhbnM7CiAgICB9CgogICAgdm9pZCBvcGVyYXRvcigpKE5vZGVfSXRyIGl0LCBOb2RlX0NJdHIgZW5kX2l0KQogICAgewogICAgICAgIGF1dG8gbD1pdC5nZXRfbF9jaGlsZCgpOwogICAgICAgIGF1dG8gcj1pdC5nZXRfcl9jaGlsZCgpOwogICAgICAgIGludCBsZWZ0PTAscmlnaHQ9MDsKICAgICAgICBpZihsIT1lbmRfaXQpIGxlZnQ9bC5nZXRfbWV0YWRhdGEoKTsKICAgICAgICBpZihyIT1lbmRfaXQpIHJpZ2h0PXIuZ2V0X21ldGFkYXRhKCk7CiAgICAgICAgY29uc3RfY2FzdDxpbnQmPihpdC5nZXRfbWV0YWRhdGEoKSk9KGxlZnQrcmlnaHQrKCppdCktPnNlY29uZCklTU9EOwogICAgfQp9OwoKdHJlZTxpbnQsaW50LGxlc3M8aW50PixyYl90cmVlX3RhZyxteV91cGRhdGVfcG9saWN5PiBtZTsKCm1haW4oKQogewogICAgI2lmbmRlZiBPTkxJTkVfSlVER0UKICAgIGZyZW9wZW4oVEFTSyIuaW4iLCJyIixzdGRpbik7CiAgICBmcmVvcGVuKFRBU0siLm91dCIsInciLHN0ZG91dCk7CiAgICAjZW5kaWYKICAgIGlvczo6c3luY193aXRoX3N0ZGlvKDApOwogICAgY2luLnRpZSgwKTsKICAgIGludCBuLGs7CiAgICBjaW4+Pm4+Pms7CiAgICB2ZWN0b3I8aW50PiBhKG4pOwogICAgZm9yKGF1dG8gJml0OmEpIGNpbj4+aXQ7CiAgICB2ZWN0b3I8aW50PiBpbnYobiwxKTsKICAgIGZvcihpbnQgaT0xO2k8aztpKyspCiAgICB7CiAgICAgICAgbWUuY2xlYXIoKTsKICAgICAgICB2ZWN0b3I8aW50PiB0KG4pOwogICAgICAgIGludCBzdW09MDsKICAgICAgICBmb3IoaW50IGk9MDtpPG47aSsrKQogICAgICAgIHsKICAgICAgICAgICAgdFtpXT1zdW0tbWUucHJlZml4X3N1bShhW2ldKStNT0Q7CiAgICAgICAgICAgIG1lLmluc2VydCh7YVtpXSxpbnZbaV19KTsKICAgICAgICAgICAgc3VtKz1pbnZbaV07CiAgICAgICAgICAgIHN1bSU9TU9EOwogICAgICAgICAgICB0W2ldJT1NT0Q7CiAgICAgICAgfQogICAgICAgIHN3YXAodCxpbnYpOwogICAgfQogICAgY291dDw8YWNjdW11bGF0ZShpbnYuYmVnaW4oKSxpbnYuZW5kKCksMGxsKSVNT0Q8PGVuZGw7CiB9