Binääripuu |
| Time limit: | 1.00 s |
| Memory limit: | 512 MB |
|
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ä)
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$
