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

#define int long long
const double PI = 3.14159265358979323846;
typedef vector<int> vint;
typedef pair<int, int> pint;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

//拡張ユークリッドの互除法
int extgcd(int a, int b, int& x, int& y) {
    int d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1;
        y = 0;
    }
    return d;
}

// mod逆元
int mod_inverse(int a, int m) {
    int x, y;
    extgcd(a, m, x, y);
    return (m + x % m) % m;
}

// 階乗、階乗逆元テーブル
int fact[1100000], fact_inv[1100000];
int mod_fact(int n, int m) {
    fact[0] = fact_inv[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = fact[i - 1] * i % m;
        fact_inv[i] = mod_inverse(fact[i], m);
    }
}

int N, K, M;
int A[33000];
int one_table[33000][440], dp[33000][440];
int imos[33000];
int mod = 1e9 + 7;

signed main() {
    cin >> N >> K >> M;
    for (int i = 0; i < M; i++)cin >> A[i];
    int whole = N - M + 1;
    for (int i = 0; i < N - M; i++)(whole *= K) %= mod;
    for (int i = 0; i < M - K + 1; i++) {
        vector<bool> check(440);
        for (int j = 0; j < K; j++) {
            if (check[A[i + j]])goto nene;
            check[A[i + j]] = true;
        }
        cout << whole << endl;
        return 0;
nene:;
    }

    one_table[0][1] = 1;
    for (int i = 1; i < 33000; i++) {
        for (int j = K - 1; j >= 1; j--)one_table[i][j] = (one_table[i - 1][j] + one_table[i][j + 1]) % mod;
        for (int j = K - 1; j >= 2; j--)(one_table[i][j] += one_table[i - 1][j - 1] * (K - j + 1) % mod) %= mod;
    }
    for (int i = 1; i < 33000; i++)dp[i][1] = imos[i] = one_table[i][1];
    for (int i = 2; i <= K - 1; i++) {
        int gy = mod_inverse(K - i + 1, mod);
        for (int j = 1; j <= 33000 - i; j++) {
            dp[j][i] = (dp[j + 1][i - 1] - imos[j] + mod) % mod * gy % mod;
            (imos[j] += dp[j][i]) %= mod;
        }
    }

    /*    for (int i = 1; i <= N; i++) {
            for (int j = 1; j < K; j++)cerr << one_table[i][j] << " ";
            cerr << endl;
        }
        cerr << endl;

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j < K; j++)cerr << dp[i][j] << " ";
            cerr << endl;
        }
        cerr << endl;*/

    bool distinct = true;
    vector<bool> check(440);
    for (int i = 0; i < M; i++) {
        if (check[A[i]])distinct = false;
        check[A[i]] = true;
    }
    if (distinct) {
        mod_fact(33000, mod);
        int ans = 0, f = fact[K - M] * fact_inv[K] % mod;
        for (int i = 0; i < N; i++) {
            int a = ans;
            for (int j = M; j <= K - 1; j++)(ans += one_table[i][j] * dp[N - i][j] % mod) %= mod;
        }
        cout << (whole - (ans * K % mod * f % mod) + mod) % mod << endl;
        return 0;
    }

    int l, r;
    check.clear();
    check.resize(440);
    for (l = 0; l < M; l++) {
        if (check[A[l]])break;
        check[A[l]] = true;
    }
    check.clear();
    check.resize(440);
    for (r = 0; r < M; r++) {
        if (check[A[M - r - 1]])break;
        check[A[M - r - 1]] = true;
    }
    int ans = 0;
    for (int i = 0; i < N - M + 1; i++) {
        (ans += dp[i + 1][l] * dp[N - M + 1 - i][r] % mod) %= mod;
    }
    cout << (whole - ans + mod) % mod << endl;

}


Measured memory_bytes: 231680