Следующие два шага, выполняемые над массивом $x$, состоящим из положительных целых чисел, называются операцией:

1. Выбрать любые два соседних элемента в $x$, уменьшить один из них на $1$, а другой сделать равным $0$.
2. Удалить все нули из $x$.

Мы называем $x$ таинственным (mystic) тогда и только тогда, когда его можно превратить в пустую последовательность за конечное число операций (возможно, ноль).

Вам дан массив $a$, состоящий из $n$ целых чисел, а также целое число $m$. Каждый элемент $a$ является либо целым числом от $1$ до $m$, либо равен $-1$. Ваша задача — заменить каждое вхождение $-1$ в $a$ на любое целое число от $1$ до $m$.

Определите количество различных таинственных массивов $a$, которые можно получить после замены. Так как ответ может быть очень большим, выведите его по модулю $10^9 + 7$.

Входные данные

Первая строка входных данных содержит два целых числа $n$ и $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^8$).

Вторая строка входных данных содержит $n$ целых чисел $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$ или $a_i = -1$).

Выходные данные

Выведите одно целое число — количество различных таинственных последовательностей $a$, которые можно получить, по модулю $10^9 + 7$.

Примеры

Пример входных данных 1

2 2
-1 -1

Пример выходных данных 1

3

Пример входных данных 2

6 10
-1 -1 -1 -1 1 7

Пример выходных данных 2

9125

Примечание

В первом примере массив $a$ равен $[-1, -1]$. Заменив обе $-1$, в качестве одного из возможных результатов получим $[1, 2]$. В этом случае мы выбираем два соседних числа: уменьшаем первое на $1$ и полагаем второе равным $0$, получая $[0, 0]$. После удаления всех нулей последовательность становится пустой. Следовательно, $[1, 2]$ — таинственная последовательность.

Аналогично, если заменить $-1$ так, чтобы получилось $[1, 1]$ или $[2, 1]$, обе эти последовательности также можно свести к пустой. Таким образом, общее количество различных таинственных последовательностей равно $3$.