Dues monedes de cada (2) P52074

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 diferents dues monedes amb el mateix valor.

Per exemple, si $x = 4$ i disposem dels dos valors 1 i 2, llavors tenim tres maneres: $1 + 1' + 2$, $1 + 1' + 2'$, i també $2 + 2'$.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $x$ i $n$, seguit de $m_1$ …$m_n$. Suposeu $1 \le n \le 1000$, $1 \le m_i \le x \le 1000$, 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. Com que el resultat pot ser molt gros, feu el càlculs mòdul $10^8 + 7$.