use proconio::input;
use std::convert::TryFrom;

// modint {{{
mod modint {
    pub trait ModValue:
        std::ops::Add<Output = Self>
        + std::ops::Sub<Output = Self>
        + std::ops::Mul<Output = Self>
        + std::ops::Div<Output = Self>
        + std::ops::Rem<Output = Self>
        + std::ops::AddAssign
        + std::ops::SubAssign
        + std::ops::MulAssign
        + std::ops::DivAssign
        + std::ops::RemAssign
        + std::ops::Neg
        + std::cmp::Ord
        + Clone
        + Copy
        + Sized
        + std::fmt::Debug
        + std::fmt::Display
    {
    }

    impl<
            Value: std::ops::Add<Output = Self>
                + std::ops::Sub<Output = Self>
                + std::ops::Mul<Output = Self>
                + std::ops::Div<Output = Self>
                + std::ops::Rem<Output = Self>
                + std::ops::AddAssign
                + std::ops::SubAssign
                + std::ops::MulAssign
                + std::ops::DivAssign
                + std::ops::RemAssign
                + std::ops::Neg
                + std::cmp::Ord
                + Clone
                + Copy
                + Sized
                + std::fmt::Debug
                + std::fmt::Display,
        > ModValue for Value
    {
    }

    pub trait Minfo: Clone + Copy + std::fmt::Debug {
        type Value: ModValue;

        fn modulus() -> Self::Value;

        fn zero() -> Self::Value;

        fn one() -> Self::Value;
    }

    #[derive(Clone, Copy, Debug)]
    pub struct Mint<Mod: Minfo>(Mod::Value);

    impl<Mod: Minfo> Mint<Mod> {
        #[inline]
        #[allow(dead_code)]
        fn is_within_the_range(x: Mod::Value) -> bool {
            Mod::zero() <= x && x < Mod::modulus()
        }

        #[inline]
        #[allow(dead_code)]
        fn normalize(x: Mod::Value) -> Mod::Value {
            if Self::is_within_the_range(x) {
                x
            } else {
                let x = x % Mod::modulus();
                if x < Mod::zero() {
                    x + Mod::modulus()
                } else {
                    x
                }
            }
        }

        #[allow(dead_code)]
        pub fn zero() -> Self {
            Self(Mod::zero())
        }

        #[allow(dead_code)]
        pub fn one() -> Self {
            Self(Mod::one())
        }

        #[allow(dead_code)]
        pub fn modulus() -> Mod::Value {
            Mod::modulus()
        }

        #[allow(dead_code)]
        pub fn is_zero(&self) -> bool {
            self.value() == Mod::zero()
        }

        #[allow(dead_code)]
        pub fn from_value(x: Mod::Value) -> Self {
            Self(Self::normalize(x))
        }

        #[allow(dead_code)]
        pub fn value(&self) -> Mod::Value {
            self.0
        }

        #[allow(dead_code)]
        pub fn inv(&self) -> Self {
            if self.is_zero() {
                panic!("inv(0)");
            }
            Self(Self::raw_inv(self.value()))
        }

        #[allow(dead_code)]
        pub fn pow(&self, b: u64) -> Self {
            Self(Self::raw_pow(self.value(), b))
        }

        fn raw_add(x: Mod::Value, y: Mod::Value) -> Mod::Value {
            let z = x + y;
            if Mod::modulus() <= z {
                z - Mod::modulus()
            } else {
                z
            }
        }

        fn raw_sub(x: Mod::Value, y: Mod::Value) -> Mod::Value {
            let z = x - y;
            if z < Mod::zero() {
                z + Mod::modulus()
            } else {
                z
            }
        }

        fn raw_neg(x: Mod::Value) -> Mod::Value {
            if x == Mod::zero() {
                Mod::zero()
            } else {
                Mod::modulus() - x
            }
        }

        fn raw_mul(x: Mod::Value, y: Mod::Value) -> Mod::Value {
            x * y % Mod::modulus()
        }

        fn raw_div(x: Mod::Value, y: Mod::Value) -> Mod::Value {
            Self::raw_mul(x, Self::raw_inv(y))
        }

        #[allow(clippy::many_single_char_names)]
        fn raw_inv(mut x: Mod::Value) -> Mod::Value {
            let mut y = Mod::modulus();
            let mut u = Mod::one();
            let mut v = Mod::zero();
            while x != Mod::zero() {
                let q = y / x;
                y -= x * q;
                v -= u * q;
                std::mem::swap(&mut x, &mut y);
                std::mem::swap(&mut u, &mut v);
            }
            Self::normalize(v)
        }

        fn raw_pow(mut a: Mod::Value, mut b: u64) -> Mod::Value {
            let mut x = Mod::one();
            while 0 < b {
                if b % 2 == 1 {
                    x = Self::raw_mul(x, a);
                }
                a = Self::raw_mul(a, a);
                b /= 2
            }
            x
        }
    }

    macro_rules! impl_biop {
        (
            $(
                $biop_trait: ident::$biop_fn: ident,
                $biop_assign_trait: ident::$biop_assign_fn: ident,
                $biop_impl: ident;
            )*
        ) => {
            $(
                impl<Mod: Minfo> std::ops::$biop_trait for Mint<Mod> {
                    type Output = Self;
                    fn $biop_fn(self, rhs: Self) -> Self::Output {
                        Mint(Self::$biop_impl(self.value(), rhs.value()))
                    }
                }
                impl<Mod: Minfo> std::ops::$biop_assign_trait for Mint<Mod>
                where
                    Self: Copy
                {
                    fn $biop_assign_fn(&mut self, rhs: Self) {
                        use std::ops::$biop_trait;
                        *self = Mint::$biop_fn(*self, rhs)
                    }
                }
            )*
        };
    }

    impl_biop! {
        Add::add, AddAssign::add_assign, raw_add;
        Sub::sub, SubAssign::sub_assign, raw_sub;
        Mul::mul, MulAssign::mul_assign, raw_mul;
        Div::div, DivAssign::div_assign, raw_div;
    }

    impl<Mod: Minfo> std::ops::Neg for Mint<Mod> {
        type Output = Self;
        fn neg(self) -> Self::Output {
            Self(Self::raw_neg(self.value()))
        }
    }

    impl<Mod: Minfo> std::cmp::PartialEq for Mint<Mod> {
        fn eq(&self, other: &Self) -> bool {
            self.value().eq(&other.value())
        }
    }
    impl<Mod: Minfo> std::cmp::Eq for Mint<Mod> {}

    impl<Mod: Minfo> std::fmt::Display for Mint<Mod> {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "{}", self.value())
        }
    }

    impl<Mod: Minfo> std::iter::Sum<Self> for Mint<Mod> {
        fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
            iter.fold(Mint::zero(), |acc, x| acc + x)
        }
    }

    impl<Mod: Minfo> std::iter::Product<Self> for Mint<Mod> {
        fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
            iter.fold(Mint::one(), |acc, x| acc * x)
        }
    }

    #[allow(dead_code)]
    pub struct Factorial<Mod: Minfo> {
        normal: Vec<Mint<Mod>>,
        inverted: Vec<Mint<Mod>>,
    }

    #[allow(dead_code)]
    impl<Mod: Minfo> Factorial<Mod>
    where
        Mod::Value: std::convert::TryFrom<usize, Error = std::num::TryFromIntError>,
    {
        pub fn new(n: usize) -> Self {
            use std::convert::TryFrom;
            let mut normal = vec![Mint::one(); n];
            for i in 1..n {
                normal[i] = normal[i - 1] * Mint::from_value(Mod::Value::try_from(i).unwrap());
            }
            let mut inverted = vec![Mint::one(); n];
            inverted[n - 1] = normal[n - 1].inv();
            for i in (1..n).rev() {
                inverted[i - 1] = inverted[i] * Mint::from_value(Mod::Value::try_from(i).unwrap());
            }
            Self { normal, inverted }
        }
    }

    #[allow(dead_code)]
    impl<Mod: Minfo> Factorial<Mod> {
        pub fn inverted(&self, i: usize) -> Mint<Mod> {
            self.inverted[i]
        }
    }

    #[allow(dead_code)]
    impl<Mod: Minfo, I: std::slice::SliceIndex<[Mint<Mod>]>> std::ops::Index<I> for Factorial<Mod> {
        type Output = I::Output;

        #[inline]
        fn index(&self, index: I) -> &Self::Output {
            &self.normal[index]
        }
    }

    #[allow(dead_code)]
    pub struct DoubleFactorial<Mod: Minfo> {
        normal: Vec<Mint<Mod>>,
        inverted: Vec<Mint<Mod>>,
    }

    #[allow(dead_code)]
    impl<Mod: Minfo> DoubleFactorial<Mod>
    where
        Mod::Value: std::convert::TryFrom<usize, Error = std::num::TryFromIntError>,
    {
        pub fn new(n: usize) -> Self {
            use std::convert::TryFrom;
            let mut normal = vec![Mint::one(); n];
            for i in 2..n {
                normal[i] = normal[i - 2] * Mint::from_value(Mod::Value::try_from(i).unwrap());
            }
            let mut inverted = vec![Mint::one(); n];
            inverted[n - 1] = normal[n - 1].inv();
            inverted[n - 2] = normal[n - 2].inv();
            for i in (2..n).rev() {
                inverted[i - 2] = inverted[i] * Mint::from_value(Mod::Value::try_from(i).unwrap());
            }
            Self { normal, inverted }
        }
    }

    #[allow(dead_code)]
    impl<Mod: Minfo> DoubleFactorial<Mod> {
        pub fn inverted(&self, i: usize) -> Mint<Mod> {
            self.inverted[i]
        }
    }

    #[allow(dead_code)]
    impl<Mod: Minfo, I: std::slice::SliceIndex<[Mint<Mod>]>> std::ops::Index<I>
        for DoubleFactorial<Mod>
    {
        type Output = I::Output;

        #[inline]
        fn index(&self, index: I) -> &Self::Output {
            &self.normal[index]
        }
    }

    #[macro_export]
    macro_rules! define_mint {
        (
            struct $modint: ident ($modinfo: ident ($modvalue: expr; $modty: ty));
        ) => {
            #[allow(dead_code)]
            #[derive(Clone, Copy, Debug)]
            pub struct $modinfo {}
            impl Minfo for $modinfo {
                type Value = $modty;
                fn modulus() -> Self::Value {
                    $modvalue
                }
                fn zero() -> Self::Value {
                    0
                }
                fn one() -> Self::Value {
                    1
                }
            }
            type $modint = Mint<$modinfo>;
        };
    }

    #[allow(dead_code)]
    #[derive(Clone, Copy, Debug)]
    pub struct Minfo1000000007 {}

    impl Minfo for Minfo1000000007 {
        type Value = i64;
        fn modulus() -> Self::Value {
            1_000_000_007
        }
        fn zero() -> Self::Value {
            0
        }
        fn one() -> Self::Value {
            1
        }
    }

    #[allow(dead_code)]
    pub type Mint1000000007 = Mint<Minfo1000000007>;

    #[allow(dead_code)]
    #[derive(Clone, Copy, Debug)]
    pub struct Minfo998244353 {}

    impl Minfo for Minfo998244353 {
        type Value = i64;
        fn modulus() -> Self::Value {
            998_244_353
        }
        fn zero() -> Self::Value {
            0
        }
        fn one() -> Self::Value {
            1
        }
    }

    #[allow(dead_code)]
    pub type Mint998244353 = Mint<Minfo998244353>;
}
// }}}

type Mint = modint::Mint1000000007;
type Minfo = modint::Minfo1000000007;

fn has_unique_subseq_of_len_k(a: &[usize], k: usize) -> bool {
    if a.len() < k {
        return false;
    }
    let mut ckd = vec![0; k];
    a[0..k].iter().for_each(|&x| ckd[x] += 1);
    let mut cnt = ckd.iter().filter(|&&x| 0 != x).count();
    if cnt == k {
        return true;
    }
    let mut l = 0;
    let mut r = k;
    while r < a.len() {
        ckd[a[l]] -= 1;
        if ckd[a[l]] == 0 {
            cnt -= 1;
        }
        if ckd[a[r]] == 0 {
            cnt += 1;
        }
        ckd[a[r]] += 1;
        l += 1;
        r += 1;
        if cnt == k {
            return true;
        }
    }
    false
}

fn solve(n: usize, k: usize, m: usize, a: &[usize]) -> Mint {
    let all = Mint::from_value((n - m + 1) as i64) * Mint::from_value(k as i64).pow((n - m) as u64);
    if has_unique_subseq_of_len_k(&a, k) {
        all
    } else {
        let mut dp = vec![vec![Mint::zero(); k]; n + 1];
        let mut ep = vec![vec![Mint::zero(); k]; n + 1];
        dp[0][0] = Mint::one();
        for i in 0..n {
            let [dp_i, dp_i_plus_one] = <&mut [_; 2]>::try_from(&mut dp[i..i + 2]).unwrap();
            let [ep_i, ep_i_plus_one] = <&mut [_; 2]>::try_from(&mut ep[i..i + 2]).unwrap();
            let mut dp_cum = Mint::zero();
            let mut ep_cum = Mint::zero();
            for j in (1..k).rev() {
                dp_i_plus_one[j] += dp_i[j - 1] * Mint::from_value((k - (j - 1)) as i64);
                ep_i_plus_one[j] += ep_i[j - 1] * Mint::from_value((k - (j - 1)) as i64);
                dp_cum += dp_i[j];
                ep_cum += ep_i[j];
                dp_i_plus_one[j] += dp_cum;
                ep_i_plus_one[j] += ep_cum;
            }
            for j in m..k {
                ep_i_plus_one[j] += dp_i_plus_one[j];
            }
            // eprintln!(
            //     "i + 1 = {}, dp_i_plus_one = {:?}, ep_i_plus_one = {:?}",
            //     i + 1,
            //     &dp_i_plus_one,
            //     &ep_i_plus_one
            // );
        }

        let fact = modint::Factorial::<Minfo>::new(k + 1);

        let l = || -> usize {
            let mut ckd = vec![false; k];
            for (i, &x) in a.iter().enumerate() {
                if ckd[x] {
                    return i;
                }
                ckd[x] = true;
            }
            m
        }();

        let r = || -> usize {
            let mut ckd = vec![false; k];
            for (i, &x) in a.iter().rev().enumerate() {
                if ckd[x] {
                    return i;
                }
                ckd[x] = true;
            }
            m
        }();

        assert_eq!(l == m, r == m);
        let a_is_unique = l == m;

        let complement = if a_is_unique {
            assert!(m <= k);
            ep[n].iter().copied().sum::<Mint>() * fact[k - m] * fact.inverted(k)
        } else {
            (0..=n - m)
                .map(|i| {
                    dp[i + l][l..].iter().copied().sum::<Mint>()
                        * fact[k - l]
                        * fact.inverted(k)
                        * dp[n - (i + m) + r][r..].iter().copied().sum::<Mint>()
                        * fact[k - r]
                        * fact.inverted(k)
                })
                .sum::<Mint>()
        };
        all - complement
    }
}

fn main() {
    input!(
        n: usize,
        k: usize,
        m: usize,
        a: [proconio::marker::Usize1; m]
    );

    println!("{}", solve(n, k, m, &a));
}

#[cfg(test)]
mod test {
    use super::*;
    fn bruteforce(n: usize, k: usize, m: usize, a: &[usize]) -> Mint {
        let number_of_seqs = std::iter::successors(Some(k), |x| Some(x * k))
            .take(n)
            .last()
            .unwrap();
        (0..number_of_seqs)
            .map(|seq_id| {
                let mut seq = vec![0; n];
                let mut x = seq_id;
                for i in 0..n {
                    seq[n - 1 - i] = (x % k) as usize;
                    x /= k;
                }
                seq
            })
            .filter(|seq_ref| has_unique_subseq_of_len_k(seq_ref, k))
            .map(|seq| {
                let ans = (0..=n - m).filter(|&i| *a == seq[i..i + m]).count();
                eprintln!("bruteforce candidate {} {:?}", ans, &seq);
                Mint::from_value(ans as i64)
            })
            .sum::<Mint>()
    }

    #[test]
    fn test() {
        for n in 1..=4 {
            for k in 1..=4 {
                for m in 1..=n.min(k) {
                    let a: Vec<_> = (0..m).collect();
                    eprintln!("{} {} {} {:?}", n, k, m, &a);
                    assert_eq!(solve(n, k, m, &a), bruteforce(n, k, m, &a));
                }
            }
        }
    }
}


Measured memory_bytes: 160412