Problem Statement

You are given integers $N, K$, and an integer sequence $A$ of length $M$.

An integer sequence where each element is between $1$ and $K$ (inclusive) is said to be colorful when there exists a contiguous subsequence of length $K$ of the sequence that contains one occurrence of each integer between $1$ and $K$ (inclusive).

For every colorful integer sequence of length $N$, count the number of the contiguous subsequences of that sequence which coincide with $A$, then find the sum of all the counts. Here, the answer can be extremely large, so find the sum modulo $10^9+7$.

Constraints

• $1 \leq N \leq 25000$
• $1 \leq K \leq 400$
• $1 \leq M \leq N$
• $1 \leq A_i \leq K$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K M
A_1 A_2 ... A_M

Output

For every colorful integer sequence of length $N$, count the number of the contiguous subsequences of that sequence which coincide with $A$, then print the sum of all the counts modulo $10^9+7$.