Kierrokset

• Time limit: 1.00 s
• Memory limit: 512 MB

Bittimaassa on $n$ kaupunkia ja niiden välillä $n-1$ tietä. Jokaisen kahden kaupungin välillä on jokin reitti.

Tehtäväsi on suunnitella turistikierros, joka alkaa kaupungista $x$, kulkee teitä pitkin ja päättyy kaupunkiin $y$. Kaksi kierrosta ovat erilaiset, jos on jokin kaupunki, jossa käyt vain toisessa kierroksista.

Montako erilaista turistikierrosta voit suunnitella?

Syöte

Syötteen ensimmäisellä rivillä on kolme kokonaislukua $n$, $x$ ja $y$. Kaupungit on numeroitu $1,2,\dots,n$.

Seuraavat $n-1$ riviä kuvaavat tiet. Kullakin rivillä on kaksi kokonaislukua $a$ ja $b$: kaupunkien $a$ ja $b$ välillä on tie.

Tuloste

Tulosta yksi kokonaisluku: erilaisten turistikierrosten määrä. Koska vastaus voi olla suuri, tulosta se modulo $10^9+7$.

Esimerkki

Syöte:
7 2 5
2 7
5 7
2 1
5 3
2 6
4 5

Tuloste:
16

Osatehtävä 1 (22 pistettä)

• $1 \leq n \leq 10$
  

Osatehtävä 2 (25 pistettä)

• $1 \leq n \leq 2 \cdot 10^5$
  
• kustakin kaupungista lähtee enintään kaksi tietä
  

Osatehtävä 3 (26 pistettä)

• $1 \leq n \leq 2 \cdot 10^5$
  
• $x = y$, eli kierros alkaa ja päättyy samassa kaupungissa
  

Osatehtävä 4 (27 pistettä)

• $1 \leq n \leq 2 \cdot 10^5$