Kui palju võimalusi?

UFOsid juhitakse hiiglaslike klaviatuuridega, millel on $N$ rida, igas reas $N$ klahvi. Iga järgmine klahvirida algab eelmisest reast poole klahvi võrra paremal.

Kaks klahvi on naabrid, kui nad puutuvad külgepidi kokku. Klahvide $A$ ja $B$ vaheline kaugus on minimaalne sammude arv, millega saab klahvilt $A$ klahvile $B$, kui igal sammul liikuda klahvilt mõnele tema naabrile. Näiteks eeloleval joonisel on klahvide ja vaheline kaugus 4.

On käimas UFOde vaheline sõda. Vaenlase UFO on just alustamas keerukat manöövrit; piloot tegi selleks $K + 1$ klahvivajutust. Et teha vastumanöövrit, oleks kasulik teada, milliseid klahve vajutati. Meie teame aga ainult esimese ja teise vajutatud klahvi vahelist kaugust, teise ja kolmanda vajutatud klahvi vahelist kaugust jne. Mitu erinevat klahvivajutuste jada sellele infole vastab?

Et tegelik vastus võib olla üüratult suur, väljastada see mooduli $10^9 + 7$ järgi.

Faili esimesel real on kaks täisarvu $N$ ja $K$ ($2 \le N \le 300$, $1 \le K \le 50$). Teisel real on $K$ tühikutega eraldatud täisarvu $A\_1$, $A\_2$, $\ldots$, $A\_K$ ($1 \le A\_i < N$), kus $A\_i$ on $i$-nda ja $i + 1$-nda vajutatud klahvi vaheline kaugus.

Faili ainsale reale väljastada üks täisarv: võimalike klahvivajutuste jadade arv mooduli $10^9 + 7$ järgi.