e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

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}
Time limit 1 second
Memory limit 256 MiB
Input example #1
4 3
2 0 1 0
Output example #1
2
Input example #2
3 5
4 0 4
Output example #2
4
Input example #3
10 103
0 0 1 0 0 9 0 0 5 7
Output example #3
403413108
Author Kostya Denisov