Dues monedes de cada (3) X92609

Donat un nombre $x$ i $n$ valors diferents de monedes $m_1$ …$m_n$, de quantes maneres es pot aconseguir canvi $x$ usant cada valor com a molt dues vegades? Considereu iguals dues monedes amb el mateix valor.

Per exemple, si $x = 4$ i disposem dels valors 1 i 2, tenim dues maneres: $1 + 1 + 2$ i $2 + 2$. Com un altre exemple, si $x = 4$ i disposem dels valors 1, 2, 3, 4 i 5, tenim cinc maneres: $1 + 1 + 3$, $1 + 2 + 2$, $1 + 4$, $2 + 3$ i 5.

Entrada

L’entrada consisteix en diversos casos, només amb nombres enters. Cada cas comença amb $x$ i $n$, seguit de $m_1$ …$m_n$. Suposeu $1 \le n \le 15$, $1 \le m_i \le x \le 10^6$, i que totes les $m_i$ són diferents.

Sortida

Per a cada cas, escriviu el nombre de maneres diferents d’aconseguir canvi exactament $x$ usant cada valor com a molt dues vegades.

Pista

Un backtracking mitjanament espurgat hauria de ser suficient.