Les deux étapes suivantes, effectuées sur un tableau $x$ composé d'entiers strictement positifs, sont appelées une opération :
- Sélectionner deux éléments adjacents quelconques dans $x$, diminuer l'un d'eux de $1$ et mettre l'autre à $0$.
- Supprimer tous les zéros de $x$.
On dit que $x$ est mystique si et seulement s'il peut être transformé en une suite vide après un nombre fini d'opérations (éventuellement zéro).
On vous donne un tableau $a$ composé de $n$ entiers, ainsi qu'un entier $m$. Chaque élément de $a$ est soit un entier compris entre $1$ et $m$, soit $-1$. Votre tâche consiste à remplacer chaque occurrence de $-1$ dans $a$ par n'importe quel entier compris entre $1$ et $m$.
Déterminez le nombre de tableaux mystiques distincts $a$ qui peuvent être obtenus après le remplacement. Comme la réponse peut être très grande, affichez-la modulo $10^9 + 7$.
Entrée
La première ligne de l'entrée contient deux entiers $n$ et $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^8$).
La deuxième ligne de l'entrée contient $n$ entiers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$ ou $a_i = -1$).
Sortie
Affichez un seul entier représentant le nombre de suites mystiques distinctes $a$ pouvant être obtenues, modulo $10^9 + 7$.
Exemples
Exemple d'entrée 1
2 2 -1 -1
Exemple de sortie 1
3
Exemple d'entrée 2
6 10 -1 -1 -1 -1 1 7
Exemple de sortie 2
9125
Note
Dans le premier exemple, le tableau $a$ est $[-1, -1]$. En remplaçant les deux $-1$, un résultat possible est $[1, 2]$. Dans ce cas, nous sélectionnons les deux nombres adjacents : nous diminuons le premier de $1$ et mettons le second à $0$, obtenant $[0, 0]$. Après avoir supprimé tous les zéros, la suite devient vide. Par conséquent, $[1, 2]$ est une suite mystique.
De même, si nous remplaçons les $-1$ par $[1, 1]$ ou par $[2, 1]$, les deux suites peuvent également être réduites à une suite vide. Par conséquent, le nombre total de suites mystiques distinctes est $3$.