Козак Вус та кольори

Вхідні дані

Перший рядок містить два цілі числа $n$ та $k$ ( $1 \leq n \leq 5 \cdot 1 0^{5}, 3 \leq k \leq 1 0^{9}$ 1 \le n \le 5 \cdot 10^5, 3 \le k \le 10^9) — кількість каменів та кількість кольорів.

Другий рядок містить $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \dots, a_n ( $0 \leq a_{i} \leq k$ 0 \le a_i \le k) — кольори каменів. Якщо $a_{i} = 0$ a_i=0, то це означає, що відповідний камінь ще не розфарбований. Якщо $1 \leq a_{i} \leq k$ 1 \le a_i \le k, то це означає, що камінь розфарбований в колір під номером $a_{i}$ a_i.

Вихідні дані

Виведіть єдине число — кількість розфарбувань каменів по модулю $1 0^{9} + 7$ 10^9+7.

Приклади

Приклад 1

Loading

Приклад 2

Loading

Приклад 3

Loading

Оцінювання

( $12$ балів): $n, k \leq 7$ n, k \le 7;
( $11$ балів): $n, k \leq 200, a_{i} = 0$ n, k \le 200, a_i=0;
( $23$ бали): $n, k \leq 200$ n, k \le 200;
( $25$ балів): $n, k \leq 3000$ n, k \le 3000;
( $29$ балів): без додаткових обмежень.