#include <bits/stdc++.h>

using namespace std;

namespace {

template <int MOD> class IntMod {
  static_assert(0 < MOD and MOD <= numeric_limits<int>::max() / 2, "MOD out of range");

  int val;

 public:

  IntMod() : val(0) {}

  IntMod(int64_t x) : val(static_cast<int>(x % MOD)) {
    if (val < 0)
      val += MOD;
  }

  IntMod& operator+=(const IntMod& x) {
    val += x.val;
    if (val >= MOD)
      val -= MOD;
    return *this;
  }

  IntMod operator+(const IntMod& x) const {
    IntMod res(*this);
    return res += x;
  }

  IntMod& operator-=(const IntMod& x) {
    val -= x.val;
    if (val < 0)
      val += MOD;
    return *this;
  }

  IntMod operator-(const IntMod& x) const {
    IntMod res(*this);
    return res -= x;
  }

  IntMod& operator*=(const IntMod& x) {
    val = static_cast<int>(static_cast<long long>(val) * x.val % MOD);
    return *this;
  }

  IntMod operator*(const IntMod& x) const {
    IntMod res(*this);
    return res *= x;
  }

  IntMod& operator/=(const IntMod& x) {
    return *this *= x.Inv();
  }

  IntMod operator/(const IntMod& x) const {
    IntMod res(*this);
    return res /= x;
  }

  IntMod operator-() const {
    IntMod res(*this);
    if (res.val != 0)
      res.val = MOD - res.val;
    return res;
  }

  /**
   * if expon is negative returns 1
   */
  IntMod Power(int expon) const {
    IntMod ans(1), temp(*this);
    for (; expon > 0; expon >>= 1) {
      if (expon & 1)
        ans *= temp;
      temp *= temp;
    }
    return ans;
  }

  /**
   *  Undefined if this value is not coprime with MOD
   */
  IntMod Inv() const {
    int64_t a = MOD, b = val, nx = 1, x = 0;
    while (b != 0) {
      tie(nx, x) = make_pair(x - (a / b) * nx, nx);
      tie(a, b) = make_pair(b, a % b);
    }
    return IntMod(x);
  }

  explicit operator int() const { return val; }

  friend ostream& operator<<(ostream& out, const IntMod& x) {
    return out << x.val;
  }

  bool operator==(const IntMod& x) const {
    return val == x.val;
  }

  bool operator!=(const IntMod& x) const {
    return val != x.val;
  }
};

#define VEVE(i, a, b) for (ll i = a, __##i = b; i < __##i; ++i)
#define DYDY(i, a, b) for (ll i = a, __##i = b; i > __##i; --i)
#define RARA(x, seq) for (auto &x : seq)
#define SIZE(x) ((ll)(x.size()))
#define ALL(x) x.begin(), x.end()

typedef int ll;
typedef double dd;
const ll MOD = ll(1e9) + 7;
typedef IntMod<MOD> Int;

void Solve(ll) {
  ll n, k, m;
  cin >> n >> k >> m;
  vector<ll> seq(m);
  RARA(s, seq) cin >> s;
  // check if s is colorful
  {
    bool is_colorful = false;
    VEVE(i, 0, m - k + 1) if (SIZE(set<ll>(seq.begin() + i, seq.begin() + i + k)) == k) {
        is_colorful = true;
      }
    if (is_colorful) {
      const Int res = Int(k).Power(n - m) * (n - m + 1);
      cout << res << endl;
      return;
    }
  }
  // s is not colorful which implies k > 1
  assert(k > 1);

  // uni_st previous elements (fixed sequence) are unique
  auto calc = [&](ll uni_st) {
    vector<vector<Int>> dp(n + 1, vector<Int>(k));
    dp[0][uni_st] = 1;
    VEVE(i, 0, n) {
      VEVE(u, 1, k) {
        // add a duplicate element
        // VEVE(j, 1, u + 1) dp[i + 1][j] += dp[i][u];
        dp[i + 1][1] += dp[i][u];
        if (u + 1 < k) dp[i + 1][u + 1] -= dp[i][u];
      }
      // accumulate
      VEVE(u, 1, k) {
        dp[i + 1][u] += dp[i + 1][u - 1];
      }
      VEVE(u, 0, k - 1) {
        // add unique element not in last u, can only do if u + 1 < k
        dp[i + 1][u + 1] += dp[i][u] * (k - u);
      }
    }
    vector<Int> res;
    VEVE(len, 0, n + 1) res.push_back(accumulate(ALL(dp[len]), Int(0)));
//    DEBUG(uni_st, res);
    return res;
  };

  // count number of occurrences in all non-colorful sequences of a length M substring that
  // consists only of unique elements (whenever u >= m in dp state)
  auto calc2 = [&]() {
    vector<vector<Int>> dp(n + 1, vector<Int>(k)), cnt(n + 1, vector<Int>(k));
    dp[0][0] = 1;
    VEVE(i, 0, n) {
      VEVE(u, 1, k) {
        // add a duplicate element
        // VEVE(j, 1, u + 1) dp[i + 1][j] += dp[i][u];
        dp[i + 1][1] += dp[i][u];
        cnt[i + 1][1] += cnt[i][u];
        if (u + 1 < k) {
          dp[i + 1][u + 1] -= dp[i][u];
          cnt[i + 1][u + 1] -= cnt[i][u];
        }
        // cnt[i + 1][m ... u] += dp[i][u]
        // sequences with at least m unique suffix get another occurrence count
        if (m <= u) {
          cnt[i + 1][m] += dp[i][u];
          if (u + 1 < k)
            cnt[i + 1][u + 1] -= dp[i][u];
        }
      }
      // accumulate
      VEVE(u, 1, k) {
        dp[i + 1][u] += dp[i + 1][u - 1];
        cnt[i + 1][u] += cnt[i + 1][u - 1];
      }
      VEVE(u, 0, k - 1) {
        // add unique element not in last u, can only do if u + 1 < k
        dp[i + 1][u + 1] += dp[i][u] * (k - u);
        cnt[i + 1][u + 1] += cnt[i][u] * (k - u);
        if (u + 1 >= m)
          cnt[i + 1][u + 1] += dp[i][u] * (k - u);
      }
    }
    Int res = 0;
    VEVE(u, 1, k) res += cnt[n][u];
    return res;
  };
  auto fact = [&](ll n) {
    Int res = 1;
    VEVE(i, 1, n + 1) res *= i;
    return res;
  };
  if (SIZE(set<ll>(ALL(seq))) == m) {
    assert(m < k);
    // all m elements of seq are unique
    // each possible length m sequence of unique elements occurs same number of times in all
    // non-colorful sequences of length n due to symmetry
    Int res = calc2();
    res /= fact(k) / fact(k - m);
    res = Int(k).Power(n - m) * (n - m + 1) - res;
    cout << res << endl;
    return;
  }
  int pref_uni = 0;
  while (pref_uni + 1 <= m and
         SIZE(set<ll>(seq.begin(), seq.begin() + pref_uni + 1)) == pref_uni + 1)
    ++pref_uni;
//  DEBUG(pref_uni);
  assert(pref_uni < k);
  const auto pref = calc(pref_uni);
  reverse(ALL(seq));
  int suff_uni = 0;
  while (suff_uni + 1 <= m and
         SIZE(set<ll>(seq.begin(), seq.begin() + suff_uni + 1)) == suff_uni + 1)
    ++suff_uni;
  assert(suff_uni < k);
  const auto suff = calc(suff_uni);
  Int res = Int(k).Power(n - m) * (n - m + 1);
  VEVE(st, 0, n - m + 1) {
    res -= pref[st] * suff[n - m - st];
  }
  cout << res << endl;
}

void Init() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
}

}

int32_t main() {
#ifdef AZN
  freopen("input.txt", "r", stdin);
#endif
  Init();
  ll tests = 1;
  VEVE(test, 1, tests + 1) Solve(test);
  return 0;
}


Measured memory_bytes: 80384