Metrou5

metrou5

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).

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$ 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.

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

* $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

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

h2. Exemplu