Dues monedes de cada (2) P52074

Donat un nombre x i n valors diferents de monedes m₁ …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₁ …m_n. Suposeu 1 ≤ n ≤ 1000, 1 ≤ m_i ≤ x ≤ 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⁸ + 7.