Hai bước sau đây, thực hiện trên một mảng $x$ gồm các số nguyên dương, được gọi là một thao tác:

1. Chọn hai phần tử kề nhau bất kỳ trong $x$, giảm một trong hai phần tử đi $1$, và gán phần tử còn lại bằng $0$.
2. Xóa tất cả các số không khỏi $x$.

Ta gọi $x$ là huyền bí (mystic) khi và chỉ khi nó có thể được biến đổi thành một dãy rỗng sau một số hữu hạn thao tác (có thể là không lần nào).

Bạn được cho một mảng $a$ gồm $n$ số nguyên, cùng với một số nguyên $m$. Mỗi phần tử của $a$ hoặc là một số nguyên từ $1$ đến $m$, hoặc là $-1$. Nhiệm vụ của bạn là thay thế mọi vị trí xuất hiện của $-1$ trong $a$ bằng một số nguyên bất kỳ từ $1$ đến $m$.

Hãy xác định số lượng mảng $a$ huyền bí phân biệt có thể nhận được sau khi thay thế. Vì kết quả có thể rất lớn, hãy in ra kết quả theo modulo $10^9 + 7$.

Dữ liệu

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n$ và $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^8$).

Dòng thứ hai của dữ liệu vào chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$ hoặc $a_i = -1$).

Kết quả

In ra một số nguyên duy nhất, biểu thị số lượng dãy $a$ huyền bí phân biệt có thể nhận được, theo modulo $10^9 + 7$.

Ví dụ

Dữ liệu mẫu 1

2 2
-1 -1

Kết quả mẫu 1

3

Dữ liệu mẫu 2

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

Kết quả mẫu 2

9125

Ghi chú

Ở ví dụ đầu tiên, mảng $a$ là $[-1, -1]$. Bằng cách thay thế cả hai số $-1$, một kết quả khả dĩ là $[1, 2]$. Trong trường hợp này, ta chọn hai số kề nhau: giảm số thứ nhất đi $1$ và gán số thứ hai bằng $0$, thu được $[0, 0]$. Sau khi xóa tất cả các số không, dãy trở thành rỗng. Do đó, $[1, 2]$ là một dãy huyền bí.

Tương tự, nếu ta thay các số $-1$ bằng $[1, 1]$ hoặc $[2, 1]$, cả hai dãy cũng có thể được rút gọn thành rỗng. Vì vậy, tổng số dãy huyền bí phân biệt là $3$.