#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;
 }