Se citesc un numar natural S (suma de platit), un numar natural m si apoi m valori reprezentand tipurile de monede disponibile (fiecare tip de moneda poate fi folosit de oricate ori). Scrieti un program care calculeaza recursiv, folosind un subprogram cu doi parametri (suma ramasa si indexul tipului de moneda curent), in cate moduri distincte (fara a tine cont de ordinea monedelor) se poate obtine suma S folosind monedele date.
- Date de intrare
- Pe prima linie S si m, pe a doua linie cele m valori ale monedelor, separate prin spatiu.
- Date de iesire
- Numarul de moduri distincte de a obtine suma S.
- Restrictii
- 0 <= S <= 30, 1 <= m <= 5, 1 <= valoare_moneda <= 30
Exemple
Exemplul 1
Intrare
0 2 1 2
Iesire
1
Exemplul 2
Intrare
5 2 1 2
Iesire
3