Aleea din fata scolii are lungimea L si trebuie sa fie pavata cu dale de forma dreptunghiulara, avand latimea egala cu latimea aleii, dar de diferite lungimi. Exista n tipuri de dale, numerotate de la 1 la n, din fiecare tip existand un numar suficient de mare de exemplare.

Cerinta

Determinati in cate moduri se poate realiza pavarea aleii cu dalele existente.

Date de intrare

Fisierul de intrare pavaj.in contine pe prima linie doua numere naturale separate printr-un spatiu: L n, unde L este lungimea aleii, iar n este numarul de tipuri de dale. Pe cea de a doua linie se afla n numere naturale nenule distincte separate prin cate un spatiu d₁ d₂ ... d_n, unde d_i reprezinta lungimea dalelor de tipul i, pentru orice i=1, n.

Date de iesire

Fisierul de iesire pavaj.out va contine o singura linie pe care va fi scris un singur numar natural, reprezentând numarul de moduri se poate realiza pavarea aleii cu dalele existente.

Restrictii si precizari

• 0<L<=700
• 0<n<=250
• 0<d_i<1000, pentru orice i=1,n.
• d_i<>d_j, pentru orice i=1,n.
• Rezultatul va avea maxim 300 de cifre.
  

Timp maxim de executie/test: 0.3 secunde

prof. Marinel Serban
Liceul de Informatica "Grigore Moisil" Iasi
Contact:marinel_serban@yahoo.com