Kui palju võimalusi?

문제

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

[이미지 1]

Kaks klahvi on naabrid, kui nad puutuvad külgepidi kokku. Klahvide $AA$ ja $BB$ vaheline kaugus on minimaalne sammude arv, millega saab klahvilt $AA$ klahvile $BB$, kui igal sammul liikuda klahvilt mõnele tema naabrile. Näiteks eeloleval joonisel on klahvide [이미지 2] ja [이미지 3] vaheline kaugus 4.

On käimas UFOde vaheline sõda. Vaenlase UFO on just alustamas keerukat manöövrit; piloot tegi selleks $K+1K\; +\; 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+710^9\; +\; 7$ järgi.

입력

Faili esimesel real on kaks täisarvu $NN$ ja $KK$ ($2\le N\le 3002\; \backslash le\; N\; \backslash le\; 300$, $1\le K\le 501\; \backslash le\; K\; \backslash le\; 50$). Teisel real on $KK$ tühikutega eraldatud täisarvu $A_{1}A\_1$, $A_{2}A\_2$, $\dots \backslash ldots$, $A_{K}A\_K$ (), kus $A_{i}A\_i$ on $ii$-nda ja $i+1i\; +\; 1$-nda vajutatud klahvi vaheline kaugus.

출력

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