Calcule

Gigel a studiat recent şirurile cu $n$ elemente, numere naturale. Pentru un astfel de şir $S$, Gigel doreşte să afle răspunsul la întrebările:

$a)$ Care este numărul minim de subşiruri strict crescătoare în care se poate partiţiona $S$?
$b)$ Care este numărul de secvenţe, modulo $20 \ 011$, cu suma elementelor divizibilă cu $k$ care se pot obţine din $S$?

Cerinţa

Dându-se un şir $S$ cu $n$ elemente numere naturale şi un număr natural $k$ se cere să se răspundă la cele două întrebări.

Date de intrare

Pe prima linie a fişierului calcule.in se află valorile naturale $n$ şi $k$ separate printr-un spaţiu. Pe următoarea linie se află cele $n$ elemente ale şirului $S$, numere naturale separate prin câte un spaţiu.

Date de ieșire

Fişierul calcule.out va conţine două linii, pe prima linie fiind scris un număr natural reprezentând răspunsul la întrebarea $a)$, iar pe a doua, un număr natural reprezentând răspunsul la întrebarea $b)$. Pentru a putea primi punctaje parțiale, fiecare linie trebuie să conțină un număr!

Restricții și precizări

• $1 < n < 100 \ 000$
• $S$ are elemente mai mici sau egale cu $20 \ 000$.
• $k < 50 \ 000$, $k < n$
• Un subşir al şirului $S$ se obţine selectând elemente din $S$ în ordinea în care sunt în $S$, dar nu obligatoriu de pe poziţii consecutive, iar o secvenţă a şirului $S$ se obţine selectând elemente în ordinea în care sunt în $S$, dar obligatoriu de pe poziţii consecutive. Se admit şi secvenţe sau subşiruri cu un singur element.
• Pentru $50\%$ din teste $k < 10 \ 000$
• Pentru răspuns corect la o singură cerinţă se acordă $50\%$ din punctaj.
• Mai multe subşiruri ale lui $S$ formează o partiţie dacă elementele reuniunii subşirurilor pot fi reaşezate astfel încât să se obţină exact $S$.
• $x$ modulo $y$ reprezintă restul împărţirii lui $x$ la $y$.

Exemplu

calcule.in

10 3         		
5 3 8 6 9 6 2 7 9 6

calcule.out

4 
23

Explicație

$a)$ O partiţie cu număr minim $(4)$ de subşiruri crescătoare este următoarea:

$5 \ 6 \ 7 \ 9$
$3 \ 6 \ 9$
$8$
$2 \ 6$

$b)$ Există $23$ de secvenţe cu suma divizibilă cu $3$. Iată două dintre acestea:

$3$
$6 \ 2 \ 7$