問題
Full many a glorious morning have I seen
Flatter the mountain-tops with sovereign eye,
Kissing with golden face the meadows green,
Gilding pale streams with heavenly alchemy;
Anon permit the basest clouds to ride
With ugly rack on his celestial face,
And from the forlorn world his visage hide,
Stealing unseen to west with this disgrace:
Even so my sun one early morn did shine
With all triumphant splendour on my brow;
But out, alack! he was but one hour mine;
The region cloud hath mask'd him from me now.
Yet him for this my love no whit disdaineth;
Suns of the world may stain when heaven's sun staineth.
Flatter the mountain-tops with sovereign eye,
Kissing with golden face the meadows green,
Gilding pale streams with heavenly alchemy;
Anon permit the basest clouds to ride
With ugly rack on his celestial face,
And from the forlorn world his visage hide,
Stealing unseen to west with this disgrace:
Even so my sun one early morn did shine
With all triumphant splendour on my brow;
But out, alack! he was but one hour mine;
The region cloud hath mask'd him from me now.
Yet him for this my love no whit disdaineth;
Suns of the world may stain when heaven's sun staineth.
── ウィリアム・シェイクスピア
ここは惑星ハーメルン。
あなたは『ハーメルン社会民主主義人民共和国連邦帝国』の皇帝の
ここには連邦を形成する$N$個の共和国がある。
また、共和国$F$から共和国$T$をつなぐ一方通行のテレポート装置が$M$個ある。またテレポートするには一回につき自分の魔力を1ポイント消費しなければならない。テレポートなので実際に道があるわけではないが問題では便宜上、テレポート装置のつながりを「道」と呼称する。
さて、あなたの魔力は『EX』──神の領域──で今Pポイント持っている。
普段はすべて魔力を使い切ることはないのだが、試しに0にしてみようと考えた。
テレポートをして国内を視察すれば皇帝としての責務も果たせるので一石二鳥である。
そのために、出発点を共和国$0$〜共和国$N-1$にしたとき、魔力を使い切る道の選び方の総和を出力してもらいたい。
例えば、N = 2だとして、魔力Pを使い切れる道の選び方が共和国$0$では3、共和国$1$でも3だった場合、3+3=6を出力すれば良い。
なお、その総和は非常に大きくなりうるので $10$$9$ $+$ $7$ で割ったあまりを出力せよ。
入力
N M P F1 T1 ... FM TM
出力
総和を出力する。制約
$1$ ≤ $N$ ≤ $50$$1$ ≤ $M$ ≤ $N*N$
$1$ ≤ $P$ ≤ $10$18
$0$ ≤ $F$$,$ $T$ < $N$
テストケース
例1
入力
4 5 2 0 1 1 2 1 3 2 3 3 0
出力
6