Dua langkah berikut, pada sebuah larik $x$ yang terdiri dari bilangan bulat positif, disebut sebagai sebuah operasi:

1. Pilih dua elemen bersebelahan mana saja di $x$, kurangi salah satunya sebesar $1$, dan ubah yang lainnya menjadi $0$.
2. Hapus semua angka nol dari $x$.

Kita menyebut $x$ mistis (mystic) jika dan hanya jika ia dapat diubah menjadi barisan kosong setelah sejumlah berhingga operasi (mungkin saja nol).

Anda diberikan sebuah larik $a$ yang terdiri dari $n$ bilangan bulat, serta sebuah bilangan bulat $m$. Setiap elemen dari $a$ merupakan bilangan bulat dari $1$ hingga $m$ atau $-1$. Tugas Anda adalah mengganti setiap kemunculan $-1$ di $a$ dengan bilangan bulat apa saja dari $1$ hingga $m$.

Tentukan banyaknya larik mistis $a$ berbeda yang dapat diperoleh setelah penggantian tersebut. Karena jawabannya bisa sangat besar, keluarkan hasilnya modulo $10^9 + 7$.

Masukan

Baris pertama masukan berisi dua bilangan bulat $n$ dan $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^8$).

Baris kedua masukan berisi $n$ bilangan bulat $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$ atau $a_i = -1$).

Keluaran

Keluarkan sebuah bilangan bulat yang menyatakan banyaknya barisan mistis $a$ berbeda yang dapat diperoleh, modulo $10^9 + 7$.

Contoh

Contoh Masukan 1

2 2
-1 -1

Contoh Keluaran 1

3

Contoh Masukan 2

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

Contoh Keluaran 2

9125

Catatan

Pada pengujian pertama, larik $a$ adalah $[-1, -1]$. Dengan mengganti kedua $-1$ tersebut, salah satu hasil yang mungkin adalah $[1, 2]$. Dalam kasus ini, kita memilih dua bilangan yang bersebelahan: kurangi bilangan pertama sebesar $1$ dan ubah bilangan kedua menjadi $0$, sehingga diperoleh $[0, 0]$. Setelah menghapus semua angka nol, barisan menjadi kosong. Oleh karena itu, $[1, 2]$ adalah barisan mistis.

Secara serupa, jika kita mengganti $-1$ tersebut menjadi $[1, 1]$ atau $[2, 1]$, kedua barisan tersebut juga dapat direduksi menjadi kosong. Dengan demikian, total banyaknya barisan mistis yang berbeda adalah $3$.