O companie are E angajati. Ziua de lucru urmatoare are un total de N minute (numerotate de la 1 la N). Fiecare angajat i stie exact cate minute poate lucra a doua zi; aceste valori sunt date de sirul x_1, x_2, ..., x_E.
Un angajat care poate lucra x minute alege un interval continuu de x minute care incepe la un minut fix si este inclus complet in cele N minute ale zilei (adica poate incepe la minutul s, cu 1 <= s <= N - x + 1, si acopera minutele s, s+1, ..., s+x-1).
Angajatii vor sa isi coordoneze alegerile astfel incat oricare doi dintre ei sa aiba cel putin un minut comun in program (nu neaparat acelasi minut comun pentru toti, ci oricare doua intervale, luate separat, sa se intersecteze).
Cate configuratii de alegeri satisfac aceasta cerinta? Deoarece raspunsul poate fi foarte mare, se cere restul acestui numar la impartirea cu 1 000 000 007. O configuratie A difera de o configuratie B daca exista cel putin un angajat care si-a ales un interval diferit in A fata de B.
- Date de intrare
- Pe prima linie se citesc doua numere naturale N si E. Pe a doua linie se citesc E numere naturale, reprezentand numarul de minute pe care le poate lucra fiecare angajat.
- Date de iesire
- Se afiseaza un singur numar natural, numarul de configuratii, modulo 1000000007.
- Restrictii
- 1 <= N <= 5000 2 <= E <= 10 1 <= x_i <= N
Exemple
Exemplul 1
Intrare
1440 7 480 360 333 1000 285 560 15
Iesire
195773645
Exemplul 2
Intrare
100 3 50 60 70
Iesire
64821