#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int MOD = 5e6, maxn = 1e5;
vector<int> sum;
void merge_sort(vector<pair<int, int> > &to_sort, vector<int> &inv, vector<int> &res, int l, int r)
{
if(r - l == 1)
return;
int m = (l + r) / 2;
merge_sort(to_sort, inv, res, l, m);
merge_sort(to_sort, inv, res, m, r);
vector<pair<int, int> > tmp;
tmp.reserve(r - l + 1);
int it1 = l, it2 = m;
int cnt = 0;
while(it1 < m || it2 < r)
{
if(it2 == r || (it1 != m && to_sort[it1].x < to_sort[it2].x))
{
tmp.push_back(to_sort[it1]);
cnt += inv[to_sort[it1].y];
if(cnt > MOD) cnt -= MOD;
it1++;
}
else
{
tmp.push_back(to_sort[it2]);
res[to_sort[it2].y] += cnt;
if(res[to_sort[it2].y] > MOD) res[to_sort[it2].y] -= MOD;
it2++;
}
}
for(int i = l; i < r; i++)
to_sort[i] = tmp[i - l];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<pair<int, int> > a(n);
vector<int> b(maxn + 1, 1);
for(int i = 0; i < n; i++)
cin >> a[i].x, a[i].y = i, a[i].x++;
for(int i = 1; i < k; i++)
{
vector<pair<int, int> > ta(a);
vector<int> tb(maxn + 1, 0);
merge_sort(ta, b, tb, 0, n);
b = tb;
}
int cnt = 0;
for(int i = 0; i < n; i++)
{
cnt += b[i];
if(cnt > MOD) cnt -= MOD;
}
cout << cnt;
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSB4IGZpcnN0CiNkZWZpbmUgeSBzZWNvbmQKCmNvbnN0IGludCBNT0QgPSA1ZTYsIG1heG4gPSAxZTU7Cgp2ZWN0b3I8aW50PiBzdW07Cgp2b2lkIG1lcmdlX3NvcnQodmVjdG9yPHBhaXI8aW50LCBpbnQ+ID4gJnRvX3NvcnQsIHZlY3RvcjxpbnQ+ICZpbnYsIHZlY3RvcjxpbnQ+ICZyZXMsIGludCBsLCBpbnQgcikKewogICAgaWYociAtIGwgPT0gMSkKICAgICAgICByZXR1cm47CiAgICBpbnQgbSA9IChsICsgcikgLyAyOwogICAgbWVyZ2Vfc29ydCh0b19zb3J0LCBpbnYsIHJlcywgbCwgbSk7CiAgICBtZXJnZV9zb3J0KHRvX3NvcnQsIGludiwgcmVzLCBtLCByKTsKICAgIHZlY3RvcjxwYWlyPGludCwgaW50PiA+IHRtcDsKICAgIHRtcC5yZXNlcnZlKHIgLSBsICsgMSk7CiAgICBpbnQgaXQxID0gbCwgaXQyID0gbTsKICAgIGludCBjbnQgPSAwOwogICAgd2hpbGUoaXQxIDwgbSB8fCBpdDIgPCByKQogICAgewogICAgICAgIGlmKGl0MiA9PSByIHx8IChpdDEgIT0gbSAmJiB0b19zb3J0W2l0MV0ueCA8IHRvX3NvcnRbaXQyXS54KSkKICAgICAgICB7CiAgICAgICAgICAgIHRtcC5wdXNoX2JhY2sodG9fc29ydFtpdDFdKTsKICAgICAgICAgICAgY250ICs9IGludlt0b19zb3J0W2l0MV0ueV07CiAgICAgICAgICAgIGlmKGNudCA+IE1PRCkgY250IC09IE1PRDsKICAgICAgICAgICAgaXQxKys7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIHRtcC5wdXNoX2JhY2sodG9fc29ydFtpdDJdKTsKICAgICAgICAgICAgcmVzW3RvX3NvcnRbaXQyXS55XSArPSBjbnQ7CiAgICAgICAgICAgIGlmKHJlc1t0b19zb3J0W2l0Ml0ueV0gPiBNT0QpIHJlc1t0b19zb3J0W2l0Ml0ueV0gLT0gTU9EOwogICAgICAgICAgICBpdDIrKzsKICAgICAgICB9CiAgICB9CiAgICBmb3IoaW50IGkgPSBsOyBpIDwgcjsgaSsrKQogICAgICAgIHRvX3NvcnRbaV0gPSB0bXBbaSAtIGxdOwoKfQoKaW50IG1haW4oKQp7CiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbygwKTsKICAgIGNpbi50aWUoMCk7CiAgICBpbnQgbiwgazsKICAgIGNpbiA+PiBuID4+IGs7CiAgICB2ZWN0b3I8cGFpcjxpbnQsIGludD4gPiBhKG4pOwogICAgdmVjdG9yPGludD4gYihtYXhuICsgMSwgMSk7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKQogICAgICAgIGNpbiA+PiBhW2ldLngsIGFbaV0ueSA9IGksIGFbaV0ueCsrOwogICAgZm9yKGludCBpID0gMTsgaSA8IGs7IGkrKykKICAgIHsKICAgICAgICB2ZWN0b3I8cGFpcjxpbnQsIGludD4gPiB0YShhKTsKICAgICAgICB2ZWN0b3I8aW50PiB0YihtYXhuICsgMSwgMCk7CiAgICAgICAgbWVyZ2Vfc29ydCh0YSwgYiwgdGIsIDAsIG4pOwogICAgICAgIGIgPSB0YjsKICAgIH0KICAgIGludCBjbnQgPSAwOwogICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgIHsKICAgICAgICBjbnQgKz0gYltpXTsKICAgICAgICBpZihjbnQgPiBNT0QpIGNudCAtPSBNT0Q7CiAgICB9CiAgICBjb3V0IDw8IGNudDsKICAgIHJldHVybiAwOwp9Cg==