- Time limit: 1.00 s
- Memory limit: 512 MB
Binääripuussa on 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 ja solmun vasemman ja oikean lapsen indeksit ovat ja . Puussa on lisäksi 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 mahdollista polkua:
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua ja : puun korkeus ja kiellettyjen kaarien määrä.
Tämän jälkeen syötteessä on kokonaislukua , kukin omalla rivillään. Luku tarkoittaa, että solmujen ja välistä kaarta ei saa kulkea. Kukin tällainen kaari annetaan kerran.
Tuloste
Tulosta yksi kokonaisluku: erilaisten polkujen määrä modulo .
Esimerkki
Syöte:
4 3 10 5 13
Tuloste:
12
Kuva vastaa esimerkkisyötettä. Kielletyt kaaret on merkitty punaisella.