#include<bits/stdc++.h>

using namespace std;
typedef long long LL;

#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}
}star;
#define DEBUG if(0)
#endif

#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}

class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};
constexpr int mod = 1e9 + 7;

constexpr int SZ = 1123456;
LL fact[SZ];
LL rfact[SZ];

inline LL invMod(LL a, LL m = mod) {
	LL b = m, u = 1, v = 0;
	while (b) {
		LL t = a / b;
		swap(a -= t * b, b);
		swap(u -= t * v, v);
	}
	return (u % m + m) % m;
}
struct fact_ {
	fact_() {
		fact[0] = 1;
		for (int i = 1; i<SZ; i++)
			fact[i] = fact[i - 1] * i%mod;
		rfact[SZ - 1] = invMod(fact[SZ - 1]);
		for (int i = SZ - 1; i>0; i--) {
			rfact[i - 1] = rfact[i] * i%mod;
		}
	}
}fact_init;

LL Perm(LL n, LL k) {
	LL u = fact[n];
	LL d = rfact[n - k] % mod;
	return u * d%mod;
}

LL Comb(LL n, LL k) {
	LL u = fact[n];
	LL d = (rfact[k] * rfact[n - k]) % mod;
	return u * d%mod;
}

LL pow_mod(LL a, LL n, int M = mod) {
	LL res = 1;
	a %= M;
	while (n) {
		if (n & 1)
			res = (res*a) % M;
		a = (a*a) % M;
		n >>= 1;
	}
	return res;
}

LL N, K, M;
LL A[1123456];

LL solve() {
	const bool isColorful = [&]() {
		map<int, int> cnt;
		for (int i : range(min(K,M))) {
			cnt[A[i]]++;
		}
		if (cnt.size() == K)return true;
		for (int i : range(K, M)) {
			cnt[A[i]]++;
			cnt[A[i - K]]--;
			if (cnt[A[i - K]] == 0)cnt.erase(A[i - K]);
			if (cnt.size() == K)return true;
		}
		return false;
	}();
	const bool isDistinct = [&]() {
		map<int, int> cnt;
		for (int i : range(M)) {
			cnt[A[i]]++;
		}
		return cnt.size() == M;
	}();

	const LL all = (N - M + 1)*pow_mod(K, N - M) % mod;
	if (isColorful) {
		// A contains colorful
		return all;
	}
	else {
		using V = vector<LL>;
		using VV = vector<V>;
		if (isDistinct) {
			// A is distinct && M < K
			VV dp(K, V(2, 0));
			dp[1][0] = K;
			if (M == 1)dp[1][1] = K;
			for (int i : range(N - 1)) {
				VV nxt(K, V(2, 0));
				for (int j : range(1,K-1)) {
					nxt[j + 1][0] = dp[j][0] * (K - j) % mod;
					nxt[j + 1][1] = dp[j][1] * (K - j) % mod;
				}
				for (int rj : range(1,K)) {
					const int j = K - 1 - rj;
					dp[j][0] = (dp[j][0] + dp[j + 1][0]) % mod;
					dp[j][1] = (dp[j][1] + dp[j + 1][1]) % mod;
				}
				for (int j : range(1, K)) {
					nxt[j][0] = (nxt[j][0] + dp[j][0]) % mod;
					nxt[j][1] = (nxt[j][1] + dp[j][1]) % mod;
					if (j >= M)nxt[j][1] = (nxt[j][0] + nxt[j][1]) % mod;
				}
				swap(dp, nxt);
			}
			LL ng = 0;
			for (int j : range(1, K)) {
				ng += dp[j][1];
			}
			ng %= mod;
			ng = ng * invMod(Perm(K, M)) % mod;
			return (all - ng + mod) % mod;
		}
		else {
			// A is not distinct
			const int suf = [&]() {
				set<int> s;
				int len = 0;
				for (int ri : range(M)) {
					const int i = M - 1 - ri;
					if (s.count(A[i]))break;
					s.insert(A[i]);
					len++;
				}
				return len;
			}();
			const int pre = [&]() {
				set<int> s;
				int len = 0;
				for (int i : range(M)) {
					if (s.count(A[i]))break;
					s.insert(A[i]);
					len++;
				}
				return len;
			}();

			VV latte(N + 1, V(2, 0));
			VV dp(K, V(2, 0));
			dp[suf][0] = 1;
			dp[pre][1] = 1;
			latte[0][0] = latte[0][1] = 1;
			for (int i : range(N)) {
				VV nxt(K, V(2, 0));
				for (int j : range(1, K - 1)) {
					nxt[j + 1][0] = dp[j][0] * (K - j) % mod;
					nxt[j + 1][1] = dp[j][1] * (K - j) % mod;
				}
				for (int rj : range(1, K)) {
					const int j = K - 1 - rj;
					dp[j][0] = (dp[j][0] + dp[j + 1][0]) % mod;
					dp[j][1] = (dp[j][1] + dp[j + 1][1]) % mod;
				}
				for (int j : range(1, K)) {
					nxt[j][0] = (nxt[j][0] + dp[j][0]) % mod;
					nxt[j][1] = (nxt[j][1] + dp[j][1]) % mod;
				}
				swap(dp, nxt);
				for (int j : range(1, K)) {
					latte[i + 1][0] += dp[j][0];
					latte[i + 1][1] += dp[j][1];
				}
				latte[i + 1][0] %= mod;
				latte[i + 1][1] %= mod;
			}
			LL ng = 0;
			for (int i : range(N - M + 1)) {
				ng += latte[i][0] * latte[N - M - i][1] % mod;
			}
			ng %= mod;
			return (all - ng + mod) % mod;
		}

	}

	
}
int main() {
	while (cin >> N >> K >> M) {
		for (int i : range(M)) {
			cin >> A[i];
		}
		cout << solve() << endl;
	}
	return 0;
}


Measured memory_bytes: 19968