Kapitan Mambeks zajmuje się badaniami dinotroli. Dinotrole to małe zwierzątka żyjące pod ziemią. Dinotrole budują skomplikowane systemy podziemnych korytarzy i komnat. Liczba komnat budowanych przez dinotrola nie przekracza trzydziestu. Komnaty są połączone jednokierunkowymi korytarzami. Dinotrole żyją w nieustannym ruchu. W każdej jednostce czasu dinotrol przemieszcza się z jednej komnaty do drugiej z wykorzystaniem wybranego przez siebie tunelu. Kapitan prowadzi badania dotyczące ruchu dinotroli. Napisz program który wczyta opis systemu korytarzy i komnat, obliczy na ile sposobów dinotrol może przejść z jednej do drugiej podanej komnat w podanej liczbie jednostek czasu.
Dane wejściowe:
W pierwszym wierszu zapisana jest liczba zestawów danych wejściowych n, n >= 0 i n <= 20. W kolejnych wierszach jest zapisanych n zestawów danych wejściowych. W pierwszym wierszu zestawu znajdują się cztery dodatnie liczby całkowite k, t, s, d: k - liczba korytarzy, t - liczba jednostek czasu 0 < t <= 1000000000, s - numer komnaty początkowej, d - numer komnaty końcowej. W kolejnych k wierszach są pary liczb k1, k2 - są to opisy korytarzy. Para liczb k1, k2 reprezentuje korytarz biegnący z komnaty o numerze k1 do komnaty o numerze k2. Wszystkie numery komnat są liczbami całkowitymi większymi od zera i mniejszymi lub równymi trzydzieści.
Dane wyjściowe:
Dla każdego zestawu program powinien wyświetlić jeden wiersz zawierający 4 ostatnie cyfry liczby sposobów przejścia dinotrola pomiędzy zadaną parą komnat w podanej liczbie jednostek czasu. Program nie powinien drukować wiodących zer.
Przykładowe dane wejściowe:
1
5 14 1 3
1 2
2 3
3 4
4 1
3 1
Przykładowe dane wyjściowe:
2