Verkossa on n solmua, jotka on numeroitu 1,2,\dots,n. Solmujen välillä on m kaarta, joita voi kulkea kumpaankin suuntaan. Seuraavassa verkossa n=4 ja m=5:

Polku solmusta toiseen voidaan esittää jonona (x_1,x_2,\dots,x_k), missä x_1 on alkusolmu, x_k on loppusolmu ja jokaisen kahden peräkkäisen solmun välillä on kaari. Esimerkiksi (1,2,4) tarkoittaa yllä olevan verkon polkua, joka kulkee ensin solmusta 1 solmuun 2 ja sitten solmusta 2 solmuun 4.

Tehtäväsi on laskea, monellako polulla solmusta 1 solmuun n solmujen määrä on melko lähellä pienintä mahdollista määrää. Tarkemmin sinun tulee laskea erilaiset polut, joissa on alle p ylimääräistä solmua.

Esimerkiksi kun p=3, sinun tulee laskea seuraavat polut yllä olevassa verkossa:

• 0 ylimääräistä solmua: (1,2,4) ja (1,3,4) (2 polkua)
• 1 ylimääräinen solmu: (1,2,3,4) ja (1,3,2,4) (2 polkua)
• 2 ylimääräistä solmua: (1,2,1,2,4), (1,2,1,3,4), (1,2,3,2,4), (1,2,4,2,4), (1,2,4,3,4), (1,3,1,2,4), (1,3,1,3,4), (1,3,2,3,4), (1,3,4,2,4), (1,3,4,3,4)
  (10 polkua)

Syöte

Ensimmäisellä rivillä on kokonaisluvut n, m ja p: solmujen määrä, kaarten määrä ja parametri p.

Seuraavat m riviä esittävät kaaret. Jokaisella rivillä on kaksi kokonaislukua a ja b: solmujen a ja b välillä on kaari.

Voit olettaa, että solmujen 1 ja n välillä on polku ja jokaisen kahden solmun välillä on enintään yksi kaari.

Tuloste

Tulosta p kokonaislukua: halutut polkujen määrät.

Polkujen määrät voivat olla suuria, joten tulosta vastaukset modulo 10^9+7.

Esimerkki

Syöte:

4 5 3
1 2
1 3
2 3
2 4
3 4

Tuloste:

2 2 10

Osatehtävä 1 (9 pistettä)

• 2 \le n \le 10
• 1 \le m \le 20
• 1 \le p \le 10

Osatehtävä 2 (19 pistettä)

• 2 \le n \le 10^5
• 1 \le m \le 2 \cdot 10^5
• p = 2

Osatehtävä 3 (22 pistettä)

• 2 \le n \le 10^5
• 1 \le m \le 2 \cdot 10^5
• p = 3

Osatehtävä 4 (18 pistettä)

• 2 \le n \le 1000
• 1 \le m \le 2000
• 1 \le p \le 10

Osatehtävä 5 (32 pistettä)

• 2 \le n \le 10^5
• 1 \le m \le 2 \cdot 10^5
• 1 \le p \le 10