CSES - Datatähti 2019 loppu - Binääripuu
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Binääripuussa on nn 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 11 ja solmun kk vasemman ja oikean lapsen indeksit ovat 2k2k ja 2k+12k+1. Puussa on lisäksi mm 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 1212 mahdollista polkua:

Syöte

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

Tämän jälkeen syötteessä on mm kokonaislukua a1,a2,,ama_1, a_2, \dots, a_m, kukin omalla rivillään. Luku aia_i tarkoittaa, että solmujen aia_i ja ai2\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 109+710^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ä)

  • 2n62 \leq n \leq 6

Osatehtävä 2 (26 pistettä)

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

Osatehtävä 3 (51 pistettä)

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