• 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