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 20011, 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

Fișierul de intrare calcule.in conține pe prima linie 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 de ieșire 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).

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