//カラフルでない数列を数えると実装が楽
#include <iostream>
#define int long long
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

int powmod(int a, int n, int mod) {
	if (n == 0) return 1;
	if (n % 2 == 0) return powmod((a * a) % mod, n / 2, mod);
	return (a * powmod(a, n - 1, mod)) % mod;
}

bool isCourful(int a[], int M, int K) {
	int i, j;
	
	for (i = 0; i < M - K + 1; i++) {
		bool used[400] = {false};
		rep(j, K) {
			used[a[i + j]] = true;
		}
		rep(j, K) if (!used[j]) break;
		if (j == K) return true;
	}
	return false;
}

bool isPartical(int a[], int M, int K) {
	int i;
	int cnt[400] = {0};
	
	rep(i, M) {
		cnt[a[i]]++;
	}
	rep(i, K) if (cnt[i] >= 2) return false;
	return true;
}

int mod = 1000000007;
int N, K, M;
int powK[25001];
int fact[25001];
int factInv[25001];
int a[25000];
int dp1[25001][402];	//dp1[i][j] = S -> (i, j), ｛長さi, 相異なる数からなるsuffixの最大長が現在j, カラフルでない｝を全て満たす数列の個数
int dp2[25001][402];	//dp2[i][j] = (i, j) -> G,｛残り長さi, 相異なる数からなるsuffixの最大長が現在j, カラフルでない｝を全て満たす数列を1つ取ったとき、
						//カラフルになるように残りi個の要素を埋める方法の数.
						//↑これらは、「カラフル列の判定法」を変形すると導出できる。

int allSearch() {
	int i, j, k;
	static int b[25000];
	int ans = 0;
	
	rep(i, N - M + 1) {
		int all = 0;
		int courful = 0;
		rep(j, powK[N]) {
			rep(k, N) {
				b[k] = (j / powK[k]) % K;
			}
			rep(k, M) {
				if (a[k] != b[i + k]) break;
			}
			if (k < M) continue;
			all++;
			if (isCourful(b, N, K)) {
				//rep(k, N) cout << b[k] << " "; cout << endl;
				courful++;
			}
		}
		//cout << "allSearch: i = " << i << ", all = " << all;
		//cout << ", courful = " << courful << ", no = " << all - courful << endl;
		ans += courful;
		ans %= mod;
	}
	return ans;
}

int solvePartical() {
	int i, j, k;
	int ret = 0;
	
	for (i = 0; i < N - M + 1; i++) {
		int ssum = 0;
		for (j = M; j < K; j++) {
			int res = dp1[i + M][j] * dp2[N - i - M][j] % mod;
			ssum += res;
			ssum %= mod;
			//cout << "i = " << i << ", j = " << j << ", dp1[" << i + M << "][" << j << "] = " << dp1[i + M][j];
			//cout << ", dp2[" << N - i - M << "][" << j << "] = " << dp2[N - i - M][j] << ", res = " << res << endl;
		}
		int all = powK[N - M] * fact[K] % mod * factInv[K - M] % mod;
		//cout << "i = " << i << ", ssum = " << ssum << ", all = " << all << endl;
		//cout << endl;
		ret += (all - ssum + mod) % mod;
		ret %= mod;
	}
	//cout << "ret = " << ret << endl;
	ret = ret * fact[K - M] % mod * factInv[K] % mod;
	return ret;
}

int solveEasy() {
	int i;
	int pre, suf;
	bool used[400];
	
	rep(i, K) used[i] = false;
	rep(i, M) {
		if (used[a[i]]) break;
		used[a[i]] = true;
	}
	pre = i;
	
	rep(i, K) used[i] = false;
	rep(i, M) {
		if (used[a[M - 1 - i]]) break;
		used[a[M - 1 - i]] = true;
	}
	suf = i;
	
	int ret = 0;
	for (i = 0; i < N - M + 1; i++) {
		int res = dp2[i][pre] * dp2[N - M - i][suf] % mod;
		res = (powK[N - M] - res + mod) % mod;
		ret += res;
		ret %= mod;
	}
	return ret;
}

signed main() {
	int n, m, f, i;
	
	cin >> N >> K >> M;
	rep(i, M) { cin >> a[i]; a[i]--; }
	
	powK[0] = 1;
	for (i = 1; i <= N; i++) powK[i] = (powK[i - 1] * K) % mod;
	fact[0] = 1;
	factInv[0] = 1;
	for (i = 1; i <= N; i++) {
		fact[i] = (fact[i - 1] * i) % mod;
		factInv[i] = powmod(fact[i], mod - 2, mod);
	}
	
	if (isCourful(a, M, K)) {
		cout << (N - M + 1) * powK[N - M] % mod << endl;
		return 0;
	}
	
	dp1[0][0] = 1;
	rep(n, N) {
		rep(m, K) {
			dp1[n + 1][1] += dp1[n][m];
			dp1[n + 1][1] %= mod;
			dp1[n + 1][m + 1] += mod - dp1[n][m];
			dp1[n + 1][m + 1] %= mod;
		}
		
		rep(m, K) {
			dp1[n + 1][m + 1] += dp1[n + 1][m];
			dp1[n + 1][m + 1] %= mod;
		}
		
		rep(m, K) {
			if (m + 1 < K) {
				dp1[n + 1][m + 1] += dp1[n][m] * (K - m);
				dp1[n + 1][m + 1] %= mod;
			}
		}
	}
	
	rep(m, K) dp2[0][m] = 1;
	for (n = 1; n <= N; n++) {
		int rui[401] = {0};
		rep(m, K) {
			rui[m + 1] = dp2[n - 1][m];
		}
		rep(m, K) {
			rui[m + 1] += rui[m];
			rui[m + 1] %= mod;
		}
		
		rep(m, K) {
			dp2[n][m] += (rui[m + 1] - rui[1] + mod) % mod;
			dp2[n][m] %= mod;
			dp2[n][m] += dp2[n - 1][m + 1] * (K - m);
			dp2[n][m] %= mod;
		}
	}
	
	if (isPartical(a, M, K)) {
		cout << solvePartical() << endl;
	}
	else {
		cout << solveEasy() << endl;
	}
	
	//cout << "AllSearch" << endl;
	//cout << allSearch() << endl;
	return 0;
}

Measured memory_bytes: 158080