Problema Secvența

Lui Algorel îi place informatica. El a învățat la școală despre secvențe de numere și despre cifra de control a unui număr. Astfel, a învățat că cifra de control a unui număr se obține efectuând suma cifrelor sale, apoi suma cifrelor acestei sume, până când suma obținută este un număr format dintr-o singură cifră. Această ultimă cifră poartă numele de cifră de control.
De exemplu, cifra de control a numărului 199 este egală cu cifra de control a numărului 19 (1 + 9 + 9), care este egală cu cifra de control a lui 10 (1 + 9), care este egală cu 1 (1 + 0).

Algorel dorește ca pentru un șir de N numere naturale x1, x2, ..., xN să identifice care sunt secvențele care au proprietatea că suma elementelor secvenței are cifra de control egală cu 9. O astfel de secvență a numit-o secvență deosebită.

Cerință

Scrieţi un program care, cunoscând N, numărul de elemente din șir, respectiv x1, x2, ..., xN, elementele din șir, rezolvă următoarele două cerințe:

1. afișează lungimea maximă a unei secvențe deosebite;
2. afișează numărul de secvențe deosebite din șir.

Date de intrare

Fişierul de intrare secventa.in conține pe prima linie două numere naturale C și N, reprezentând cerința care trebuie rezolvată (1 sau 2), respectiv lungimea șirului. Următoarea linie conține N numere naturale x1, x2, ..., xN separate prin câte un spațiu, reprezentând elementele din șir.

Date de ieșire

Fişierul de ieşire secventa.out va conţine pe prima linie un singur număr natural, reprezentând răspunsul la cerința C din fișierul de intrare.

Restricții și precizări

• 1 ≤ N ≤ 1 000 000;
• 0 ≤ xi ≤ 1 000, pentru oricare 1 ≤ i ≤ N;
• Se garantează pentru toate datele de test că există cel puțin o secvență deosebită;
• O secvenţă dintr-un şir este formată din elemente aflate pe poziţii consecutive în şirul dat;
• Pentru rezolvarea corectă a cerinţei 1 se acordă 40% din punctaj, iar pentru rezolvarea corectă a cerinţei 2 se acordă 60% din punctaj.

Exemple