| Fişierul intrare/ieşire: | metrou5.in, metrou5.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" 17 |
| Autor | Florin Chirica | Adăugată de |  AGMInformatica •AGMinformatica |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 36774 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | metrou5.out |
|---|---|
| 6 5 -1 -1 1 -1 -1 -1 | 35 |
