Se citesc n numere naturale si un numar natural nenul M. Determinati, folosind Programarea Dinamica, cate submultimi NEVIDE ale celor n numere au suma un multiplu al lui M.
- Date de intrare
- Pe prima linie se citesc n si M. Pe a doua linie se citesc cele n numere.
- Date de iesire
- Se afiseaza un singur numar: numarul de submultimi nevide cu suma multiplu de M.
- Restrictii
- 1 <= n <= 40, 1 <= M <= 100, 0 <= element <= 10^9
Exemple
Exemplul 1
Intrare
3 3 3 6 9
Iesire
7
Exemplul 2
Intrare
4 5 1 2 3 4
Iesire
3