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

Нещодавно Козак Вус знайшов $n$ каменів, розташованих у ряд. Також в нього є $k$ різних фарб пронумерованих від $1$ до $k$.

Козак Вус хоче розфарбувати камені так, щоб не було двох сусідніх каменів з однаковим кольором. На жаль, деякі камені вже розмальовані.

Козаку Вусу цікаво скільки існує способів розфарбувати ці камені, щоб виконувалась умова вище. При чому не можна перефарбовувати вже розмальовані камені.

Оскільки відповідь може бути дуже великою, то виведіть її остачу від ділення на $10^9+7$.

Вхідні дані

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

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

Вихідні дані

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

Приклади

Оцінювання

1. ($12$ балів): $n,k\le 7$;

2. ($11$ балів): $n,k\le 200,a_i=0$;

3. ($23$ бали): $n,k\le 200$;

4. ($25$ балів): $n,k\le 3000$;

5. ($29$ балів): без додаткових обмежень.