Fişierul intrare/ieşire:metrou5.in, metrou5.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 17
AutorFlorin ChiricaAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test0.2 secLimită de memorie36774 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Metrou5

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.

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

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.

Date de ieşire

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

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ K ≤ 100.000
  • 1 ≤ valuei ≤ K sau valuei este -1 daca numarul de pe pozitia i este ascuns

Exemplu

metrou5.inmetrou5.out
6 5
-1 -1 1 -1 -1 -1
35
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?