eolymp
Соревнования

Ukrainian Selection Camp to the European Girls' Olympiad in Informatics 2021

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

Нещодавно Козак Вус знайшов $n$ каменів, розташованих у ряд. Також в нього є $k$ різних фарб пронумерованих від $1$ до $k$. Козак Вус хоче розфарбувати камені так, щоб не було двох сусідніх каменів з однаковим кольором. На жаль, деякі камені вже розмальовані. Козаку Вусу цікаво скільки існує способів розфарбувати ці камені, щоб виконувалась умова вище. При чому не можна перефарбовувати вже розмальовані камені. Оскільки відповідь може бути дуже великою, то виведіть її остачу від ділення на $10^9+7$. \InputFile Перший рядок містить два цілі числа $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$. \OutputFile Виведіть єдине число --- кількість розфарбувань каменів по модулю $10^9+7$. \Scoring \begin{enumerate} \item ($12$ балів): $n, k \le 7$; \item ($11$ балів): $n, k \le 200, a_i=0$; \item ($23$ бали): $n, k \le 200$; \item ($25$ балів): $n, k \le 3000$; \item ($29$ балів): без додаткових обмежень. \end{enumerate}
Лимит времени 1 секунда
Лимит использования памяти 256 MiB
Входные данные #1
4 3
2 0 1 0
Выходные данные #1
2
Входные данные #2
3 5
4 0 4
Выходные данные #2
4
Входные данные #3
10 103
0 0 1 0 0 9 0 0 5 7
Выходные данные #3
403413108
Автор Kostya Denisov