Los siguientes dos pasos, realizados sobre un arreglo $x$ compuesto por enteros positivos, se denominan una operación:
- Seleccionar dos elementos adyacentes cualesquiera en $x$, disminuir uno de ellos en $1$ y establecer el otro en $0$.
- Eliminar todos los ceros de $x$.
Llamamos a $x$ místico si y solo si puede transformarse en una secuencia vacía tras un número finito de operaciones (posiblemente cero).
Se te da un arreglo $a$ compuesto por $n$ enteros, así como un entero $m$. Cada elemento de $a$ es o bien un entero de $1$ a $m$ o bien $-1$. Tu tarea es reemplazar cada aparición de $-1$ en $a$ por cualquier entero de $1$ a $m$.
Determina el número de arreglos místicos distintos $a$ que se pueden obtener después del reemplazo. Como la respuesta puede ser muy grande, imprímela módulo $10^9 + 7$.
Entrada
La primera línea de la entrada contiene dos enteros $n$ y $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^8$).
La segunda línea de la entrada contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$ o $a_i = -1$).
Salida
Imprime un solo entero, que represente el número de secuencias místicas distintas $a$ que se pueden obtener, módulo $10^9 + 7$.
Ejemplos
Entrada de ejemplo 1
2 2 -1 -1
Salida de ejemplo 1
3
Entrada de ejemplo 2
6 10 -1 -1 -1 -1 1 7
Salida de ejemplo 2
9125
Nota
En la primera prueba, el arreglo $a$ es $[-1, -1]$. Al reemplazar ambos $-1$, un resultado posible es $[1, 2]$. En este caso, seleccionamos los dos números adyacentes: disminuimos el primero en $1$ y establecemos el segundo en $0$, obteniendo $[0, 0]$. Después de eliminar todos los ceros, la secuencia queda vacía. Por lo tanto, $[1, 2]$ es una secuencia mística.
Del mismo modo, si reemplazamos los $-1$ con $[1, 1]$ o con $[2, 1]$, ambas secuencias también pueden reducirse a una secuencia vacía. Por lo tanto, el número total de secuencias místicas distintas es $3$.