I seguenti due passaggi, su un array $x$ composto da interi positivi, sono chiamati un'operazione:

1. Seleziona due elementi adiacenti qualsiasi in $x$, diminuisci uno di essi di $1$ e imposta l'altro a $0$.
2. Rimuovi tutti gli zeri da $x$.

Chiamiamo $x$ mistico se e solo se può essere trasformato in una sequenza vuota dopo un numero finito di operazioni (eventualmente zero).

Ti viene dato un array $a$ composto da $n$ interi, oltre a un intero $m$. Ogni elemento di $a$ è un intero da $1$ a $m$ oppure $-1$. Il tuo compito è sostituire ogni occorrenza di $-1$ in $a$ con un qualsiasi intero da $1$ a $m$.

Determina il numero di array mistici distinti $a$ che possono essere ottenuti dopo la sostituzione. Poiché la risposta può essere molto grande, stampala modulo $10^9 + 7$.

Input

La prima riga dell'input contiene due interi $n$ e $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^8$).

La seconda riga dell'input contiene $n$ interi $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$ oppure $a_i = -1$).

Output

Stampa un singolo intero, che rappresenta il numero di sequenze mistiche distinte $a$ che possono essere ottenute, modulo $10^9 + 7$.

Esempi

Input di esempio 1

2 2
-1 -1

Output di esempio 1

3

Input di esempio 2

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

Output di esempio 2

9125

Note

Nel primo test, l'array $a$ è $[-1, -1]$. Sostituendo entrambi i $-1$, un risultato possibile è $[1, 2]$. In questo caso, selezioniamo i due numeri adiacenti: diminuiamo il primo di $1$ e impostiamo il secondo a $0$, ottenendo $[0, 0]$. Dopo aver rimosso tutti gli zeri, la sequenza diventa vuota. Pertanto, $[1, 2]$ è una sequenza mistica.

Analogamente, se sostituiamo i $-1$ con $[1, 1]$ o con $[2, 1]$, entrambe le sequenze possono anch'esse essere ridotte a una sequenza vuota. Pertanto, il numero totale di sequenze mistiche distinte è $3$.