- Time limit: 1.00 s
- Memory limit: 512 MB
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ö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$
- $2 \leq n \leq 60$
- $m = 0$
- $2 \leq n \leq 60$
- $0 \leq m \leq 10^5$