#include <bits/stdc++.h>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

template<class T> ostream& operator<<(ostream& os, const V<T> &v) {
    os << "[";
    for (auto p: v) os << p << ", ";
    os << "]";
    return os;
}

template<uint MD>
struct ModInt {
    using M = ModInt;
    uint v;
    ModInt() : v{0} {}
    ModInt(ll _v) : v{normS(_v%MD+MD)} {}
    explicit operator bool() const {return v != 0;}
    static uint normS(uint x) {return (x<MD)?x:x-MD;};
    static M make(uint x) {M m; m.v = x; return m;}
    static M inv(const M &x) {return x.pow(MD-2); }
    M operator+(const M &r) const {return make(normS(v+r.v));}
    M operator-(const M &r) const {return make(normS(v+MD-r.v));}
    M operator*(const M &r) const {return make(ull(v)*r.v%MD);}
    M operator/(const M &r) const {return *this*inv(r);}
    M& operator+=(const M &r) {return *this=*this+r;}
    M& operator-=(const M &r) {return *this=*this-r;}
    M& operator*=(const M &r) {return *this=*this*r;}
    M& operator/=(const M &r) {return *this=*this/r;}
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
};
using Mint = ModInt<TEN(9)+7>;
ostream& operator<<(ostream& os, Mint m) {
    return os << m.v;
}

//const int D = 30;
const int D = 30000;
V<Mint> make(int k, int s) {
    V<Mint> res(D);
    V<Mint> nw(k+1); nw[s] = Mint(1);
    for (int ph = 1; ph < D; ph++) {
        res[ph] = res[ph-1] * Mint(k);
        V<Mint> nnw(k+1);
        for (int i = 0; i < k; i++) {
            nnw[i+1] += nw[i] * Mint(k-i);
        }
        Mint sm = Mint(0);
        for (int i = k-1; i >= 1; i--) {
            sm += nw[i];
            nnw[i] += sm;
        }
        res[ph] += nnw[k]; nnw[k] = Mint(0);
        nw = nnw;
    }
    return res;
}


Mint solve1(int n, int k, int s) {
    using A = array<Mint, 2>;
    V<A> nw(k+1); nw[0][0] = Mint(1);
    V<A> res(k+1);
    for (int ph = 0; ph < n; ph++) {
        V<A> nnw(k+1), nres(k+1);
        for (int f = 0; f < 2; f++) {
            for (int i = 0; i < k; i++) {
                nnw[i+1][f] += nw[i][f] * Mint(k-i);
                nres[i+1][f] += res[i][f] * Mint(k-i);
            }
            Mint sm = Mint(0), rsm = Mint(0);
            for (int i = k; i >= 1; i--) {
                sm += nw[i][f];
                nnw[i][f] += sm;
                rsm += res[i][f];
                nres[i][f] += rsm;
            }
        }

        nnw[k][1] += nnw[k][0]; nnw[k][0] = Mint(0);
        nres[k][1] += nres[k][0]; nres[k][0] = Mint(0);
        for (int f = 0; f < 2; f++) {
            for (int i = s; i <= k; i++) {
                nres[i][f] += nnw[i][f];
            }
        }

        nw = nnw;
        res = nres;
    }
    Mint ans;
    for (int i = 0; i <= k; i++) {
        ans += res[i][1];
    }
    return ans;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(20) << fixed;

    int n, k, m;
    cin >> n >> k >> m;
    V<int> a(m);
    for (int i = 0; i < m; i++) cin >> a[i];

    // array contain perm
    if (k <= m) {        
        map<int, int> mp;
        for (int i = 0; i < k; i++) {
            mp[a[i]]++;
        }
        bool f = false;
        for (int i = k; i <= m; i++) {
            if (int(mp.size()) == k) {
                f = true;
                break;
            }
            if (i == m) break;
            mp[a[i]]++;
            mp[a[i-k]]--;
            if (mp[a[i-k]] == 0) mp.erase(a[i-k]);
        }
        if (f) {
            Mint ans = Mint(k).pow(n-m);
            ans *= Mint(n-m+1);
            cout << ans.v << endl;
            return 0;
        }
    }
    
    // all distinct
    if (int(set<int>(begin(a), end(a)).size()) == m) {
        Mint ans = solve1(n, k, m);
        for (int i = k-m+1; i <= k; i++) ans /= Mint(i);
        cout << ans.v << endl;
        return 0;
    }

    int l = 0, r = m;
    {
        set<int> s;
        while (!s.count(a[l])) {
            s.insert(a[l]); l++;
        }
    }
    {
        set<int> s;
        while (!s.count(a[r-1])) {
            s.insert(a[r-1]); r--;
        }
    }
    V<Mint> le = make(k, l);
    V<Mint> ri = make(k, m-r);
    Mint sm;
    Mint al = Mint(k).pow(n-m);

    for (int i = 0; i <= n-m; i++) {
        Mint lx = Mint(k).pow(i) - le[i];
        Mint rx = Mint(k).pow(n-m-i) - ri[n-m-i];
        sm += al - lx * rx;
    }
    cout << sm.v << endl;
    return 0;
}


Measured memory_bytes: 640