Remplissage du tableau
Étant donné un tableau de
n éléments, vous savez que toutes les valeurs de ce tableau se situent entre 1 et m. De plus, la différence absolue entre deux éléments adjacents est au maximum 1. Certaines valeurs du tableau ont été effacées et vous devez déterminer le nombre de façons différentes de remplir ces cases manquantes sans enfreindre les conditions.Entrée
La première ligne de l'entrée contient deux entiers
n (1 ≤ n ≤ ) et m (1 ≤ m ≤ 100).La ligne suivante contient
n entiers séparés par des espaces (1 ≤ ≤ m), qui représentent les éléments du tableau. La valeur de égale à 0 indique qu'il s'agit d'une valeur effacée à la position i.Sortie
Le programme doit afficher le nombre de manières de remplir le tableau tout en respectant les conditions. Comme ce nombre peut être très grand, on demande de l'afficher modulo .
Exemples
Entrée | Sortie |
3 5
2 0 2 | 3 |
Explication
- 2 1 2
- 2 2 2
- 2 3 2
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB