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

struct BipartiteGraph {
	struct Edge {
		const int from;
		const int to;
		Edge(const int from, const int to) :
			from(from),
			to(to)
			{}
	};
	const int V;
	vector<vector<Edge>> G;
	vector<int> color;
	BipartiteGraph(const int V) :
		V(V),
		G(vector<vector<Edge>>(V, vector<Edge>())),
		color(vector<int>(V, -1))
		{}
	void addEdge(const int from, const int to) {
		G[from].emplace_back(from, to);
		G[to].emplace_back(to, from);
	}
	bool dfs(const int from, const int col) {
		color[from] = col;
		bool ret = true;
		for(Edge e : G[from]) {
			if(color[e.to] == -1) {
				ret &= dfs(e.to, col ^ 1);
			}
			if(color[e.to] == col) {
				return false;
			}
		}
		return ret;
	}
	int bipart() {
		if(not dfs(0, 0)) throw "NOT Bipartite Graph";
		int ret = 0;
		for(int i : color) ret += i;
		return ret;
	}
};

struct UnionFind {
	const int V;
	// par[x] := xのroot
	vector<int> par;
	// sz[x] := xを含む集合のサイズ
	vector<int> sz;
	UnionFind(const int V) :
		V(V),
		par(vector<int>(V)),
		sz(vector<int>(V, 1))
		{
			for(int i = 0; i < V; ++i) par[i] = i;
		}
	bool unite(int x, int y) {
		x = root(x), y = root(y);
		if(same(x, y)) return false;
		if(y < x) swap(x, y);
		par[y] = x;
		sz[x] += sz[y];
		return true;
	}
	int root(int x) {
		if(par[x] == x) return x;
		return (par[x] = root(par[x]));
	}
	bool same(int x, int y) {
		return (root(x) == root(y));
	}
	int size(int x) {
		return sz[root(x)];
	}
};

int dp[5010][5010];
int main() {
	const int MOD = 1e9 + 7;
	int n, m; cin >> n >> m;
	int a[n];
	for(int i = 0; i < n; ++i) {
		cin >> a[i];
		--a[i];
	}
	UnionFind uf(n);
	for(int i = 0; i < n; ++i) {
		for(int j = i + 1; j < n; ++j) {
			if(a[i] > a[j]) uf.unite(i, j);
		}
	}
	vector<int> edge[n];
	for(int i = 0; i < n; ++i) {
		edge[uf.root(i)].push_back(i);
	}
	vector<int> color[2];
	for(int i = 0; i < n; ++i) {
		int nn = edge[i].size();
		if(nn == 0) continue;
		BipartiteGraph bg(nn);
		for(int j = 0; j < nn; ++j) {
			for(int k = j + 1; k < nn; ++k) {
				if(a[edge[i][j]] > a[edge[i][k]]) {
					bg.addEdge(j, k);
				}
			}
		}
		try {
			int x = bg.bipart();
			color[0].push_back(x);
			color[1].push_back(nn - x);
		}
		catch(...) {
			cout << 0 << endl;
			return 0;
		}
	}
	int sz = color[0].size();
	dp[0][0] = 1;
	for(int i = 1; i <= sz; ++i) {
		for(int j = 0; j <= n; ++j) {
			for(int k = 0; k < 2; ++k) {
				if(j - color[k][i - 1] >= 0) {
					dp[i][j] += dp[i - 1][j - color[k][i - 1]];
				}
				dp[i][j] %= MOD;
			}
		}
	}
	int ans = 0;
	for(int j = 0; j <= n; ++j) {
		if(max(j, n - j) > m) continue;
		ans += dp[sz][j];
		ans %= MOD;
	}
	cout << ans << endl;
	return 0;
}


