Наступні два кроки над масивом $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$.