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

Gigel a studiat recent sirurile cu $n$ elemente, numere naturale. Pentru un astfel de sir $S$, Gigel doreste sa afle raspunsul la intrebarile:
 
# Care este numarul minim de subsiruri strict crescatoare in care se poate partitiona $S$?
# Care este numarul de secvente, modulo $20011$, cu suma elementelor divizibila cu $k$ care se pot obtine din $S$?
 
h2. Cerinta
 
Dandu-se un sir $S$ cu $n$ elemente numere naturale si un numar natural $k$ se cere sa se raspunda la cele doua intrebari.

Poveste şi cerinţă...

h2. Date de intrare

Pe prima linie a fisierului $calcule.in$ se afla valorile naturale $n$ si $k$ separate printr-un spatiu. Pe urmatoarea linie se afla cele $n$ elemente ale sirului $S$, numere naturale separate prin cate un spatiu.

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

h2. Date de ieşire

Fisierul $calcule.out$ va contine doua linii, pe prima linie fiind scris un numar natural reprezentand raspunsul la intrebarea $1)$, iar pe a doua, un numar natural reprezentand raspunsul la intrebarea $2)$.

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

h2. Restricţii

* $1 < n < 100 000$
 
* $S$ are elemente mai mici sau egale cu $20 000$
 
* $k < 50 000$, $k < n$
 
* Un subsir al sirului $S$ se obtine selectand elemente din $S$ in ordinea in care sunt in $S$, dar nu obligatoriu de pe pozitii consecutive, iar o secventa a sirului $S$ se obtine selectand elemente in ordinea in care sunt in $S$, dar obligatoriu de pe pozitii consecutive. Se admit si secvente sau subsiruri cu un singur element.
 
* Pentru $50%$ din teste $k < 10 000$
 
* Pentru raspuns corect la o singura cerinta se acorda $50%$ din punctaj.
 
* Mai multe subsiruri ale lui $S$ formeaza o partitie daca elementele reuniunii subsirurilor pot fi reasezate astfel incat sa se obtina exact $S$.
 
* $x modulo y$ reprezinta restul impartirii lui $x$ la $y$.
 
* In situatia in care nu ati reusit sa rezolvati cerinta $1)$, dar aveti un raspuns pentru $2)$, veti scrie raspunsul pentru cerinta $2)$ pe linia $2$ si nu pe prima linie!

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

h2. Exemplu
table(example). |_. calcule.in |_. calcule.out |

| 10 3
5 3 8 6 9 6 2 7 9 6
| 4
  23

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

# O partitie cu numar minim ( $4$ ) de subsiruri crescatoare este urmatoarea:
$5 6 7 9$
$3 6 9$
$8$
$2 6$
# Exista $23$ de secvente cu suma divizibila cu $3$. Iata doua dintre acestea:
$3$
$6 2 7$

...

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

9943