Rezolvare PBinfo #4186

Cerința

Se dau n numere naturale reprezentând valorile unor monede și S reprezentând o sumă de bani. Să se afișeze numărul de modalități de a plăti suma cu cele n valori.

Date de intrare

Programul citește de la tastatură numărul S, apoi numărul n, iar apoi n numere naturale, separate prin spații reprezentând valorile celor n monede.

Date de ieșire

Programul va afișa pe ecran numărul m, reprezentând numărul de modalități de a plăti suma S.

Restricții și precizări

• 1≤ S ≤ 250
• 1 ≤ n ≤ 100
• cele n numere citite sunt distincte și vor fi mai mici decât 100

Exemplu:

Intrare

4 3
1 2 3

Ieșire

4

Explicație

Sunt 4 modalităti de a plăti suma 4:
{1,1,1,1}
{1,1,2}
{1,3}
{2,2}