#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 10114;
int t[N];

int n, m;

int lowbit(int x)
{
	return x & -x;
}

void change(int x, int k)
{
	while(x <= n)
	{
		t[x] += k;
		x += lowbit(x);
	}
}

int ask(int x)
{
	if(x == 0)
		return 0;
	return t[x] + ask(x - lowbit(x));
}

int T;
int a[N], b[N];
int f[N][20];

signed main()
{
	scanf("%lld%lld", &n, &m);
	m += 1;
	for(int i = 1; i <= n; i = i + 1)
		scanf("%lld", &a[i]), b[i] = a[i];
	sort(b + 1, b + 1 + n);
	for(int i = 1; i <= n; i = i + 1)
		a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b + 1;
	for(int j = 1; j <= m; j = j + 1)
	{
		memset(t, 0, sizeof(t));
		if(j == 1)
			change(1, 1);
		for(int i = 1; i <= n; i = i + 1)
		{
			f[i][j] = ask(a[i] - 1);
			change(a[i], f[i][j - 1]);
		}
	}
	long long ans = 0;
	for(int i = m; i <= n; i = i + 1)
		ans += f[i][m];
	printf("%lld\n", ans);
	return 0;
}