Казак Вус и цвета

Казак Вус недавно нашел $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$ баллов): без дополнительных ограничений.