metrou5

Metrou5

== include(page="template/taskheader" task_id="metrou5") ==

Poveste şi cerinţă...

In regatul Smecheriei, reteaua de metrou este una foarte generoasa, avand de asemenea si huligani pe masura. Fiind vorba de un regat ca cel al lui Verde-Imparat sau macar ca cel al fratelui sau mai fraier, Ros-Imparat, gesturile huliganesti sunt la ordinea zilei. Intr-o zi, un frumos merge la metrou si vede un sir de numere naturale cu valori intre $1$ si $K$ scrise pe peron. Evident, comportamentul sau incontrolabil il determina sa sfasie tot ce vede in cale. Mai tarziu, uitandu-se la ramasitele sirului, se gandeste in cate moduri il poate completa cu numere cuprinse intre $1$ si $K$ pentru ca sirul obtinut sa fie crescator.
 
h2. Cerinta
 
Dandu-vi-se un sir de $N$ numere cu valori cuprinse intre $1$ si $K$ si cu valori lipsa (marcate cu -1 in sir), trebuie sa spuneti in cate feluri $modulo 1.000.000.007$ se pot completa pozitiile lipsa cu numere cuprinse tot intre $1$ si $K$ astfel incat sirul obtinut sa fie crescator (atentie, nu strict crescator).

h2. Date de intrare

Fişierul de intrare $metrou5.in$ ...

Fişierul de intrare $metrou5.in$ va contine pe prima linie doua numere naturale, $N$ si $K$. Pe a doua linie va contine $N$ valori, anume elementele sirului initial sau $-1$ daca acestea au fost sfasiate de huligan.

h2. Date de ieşire

În fişierul de ieşire $metrou5.out$ ...

În fişierul de ieşire $metrou5.out$ va contine numarul cerut.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100.000$
* $1 ≤ K ≤ 100.000$
* $1 ≤ value[~i~] ≤ K$ sau $value[~i~]$ este $-1$ daca numarul de pe pozitia $i$ este ascuns

h2. Exemplu
table(example). |_. metrou5.in |_. metrou5.out |
| 6 5
-1 -1 1 -1 -1 -1

| This is another
  text written on
  multiple lines.

| 35

|

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="metrou5") ==