Binääripuussa on n tasoa ja puu on täydellinen, eli jokaisella solmulla on kaksi lasta alinta tasoa lukuun ottamatta. Puun solmut on indeksoitu niin, että juuren indeksi on 1 ja solmun k vasemman ja oikean lapsen indeksit ovat 2k ja 2k+1. Puussa on lisäksi m kiellettyä kaarta, joita pitkin ei saa kulkea.

Puusta muodostetaan verkko peilaamalla se lehtisolmuista. Monellako tavalla verkossa voi muodostaa polun, joka alkaa ja päättyy alkuperäisen puun juuressa, sisältää vähintään yhden kaaren eikä kulje monta kertaa saman kaaren kautta?

Esimerkiksi seuraavassa verkossa on 12 mahdollista polkua:

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja m: puun korkeus ja kiellettyjen kaarien määrä.

Tämän jälkeen syötteessä on m kokonaislukua a_1, a_2, \dots, a_m, kukin omalla rivillään. Luku a_i tarkoittaa, että solmujen a_i ja \left \lfloor{\frac{a_i}{2}}\right \rfloor välistä kaarta ei saa kulkea. Kukin tällainen kaari annetaan kerran.

Tuloste

Tulosta yksi kokonaisluku: erilaisten polkujen määrä modulo 10^9+7.

Esimerkki

Syöte:

4 3
10
5
13

Tuloste:

12

Kuva vastaa esimerkkisyötettä. Kielletyt kaaret on merkitty punaisella.

Osatehtävä 1 (23 pistettä)

• 2 \leq n \leq 6

Osatehtävä 2 (26 pistettä)

• 2 \leq n \leq 60
• m = 0

Osatehtävä 3 (51 pistettä)

• 2 \leq n \leq 60
• 0 \leq m \leq 10^5