407294: GYM102756 I Space and Time and Music

In the distant future, Ellen works as a musician for the Willbeington D.C. Philharmonic. However, frequent use of time travel has caused the Fabric of Space and Time to weaken considerably, to the extent that certain melodies can cause severe vibrations and harm the musician playing them, as well as the Fabric itself. To prevent such harm, the Ministry of Music has created a handy guidebook for composing melodies, which details which instruments can follow which other instruments, as well as how many notes can be played on any given instrument.

Unfortunately, this guidebook was greeted by large amounts of backlash from people that believed that the Ministry of Music was suffocating their creative spirit in making music, and was just a power grab on the part of the Minister for Music. In response to concerns that the guidebook was limiting the supply of fresh melodies, Ellen decides to enumerate all the possible melodies that can be written that still follow the guidebook.

Since the guidebook has no restrictions on length of melody, this number is possibly infinite. So, Ellen restricts her count to only consider melodies of length $$$K$$$, and ones starting with the $$$S$$$'th instrument.

Given the guidebook, the starting instrument, and the number of notes, find the answer for Ellen. Because the number of possible melodies might be very large, output the answer$$$\mod{10^9 +7}$$$.

The first line of input contains four integers, $$$N, M, K, S$$$ ($$$1 \le N \le 50$$$, $$$1\le M \le N^2$$$, $$$1\le K \le 10^6$$$, $$$0\le S\le N-1$$$) - the number of distinct instruments, the number of ordered pairs of instruments that can follow each other, the number of notes in the melody being constructed, and the index of the starting instrument.

The second line contains $$$N$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 10^6$$$) — the number of notes the $$$i$$$th instrument can play.

Finally, $$$M$$$ lines follow, where the $$$j$$$th line is of the form $$$x_j\ y_j$$$ ($$$0\le x_j, y_j \le N-1$$$), indicating that the $$$y_j$$$'th instrument can follow the $$$x_j$$$'th instrument.

Output a single integer equal to the number of total melodies that can be created following the rules of the guidebook that start with instrument $$$S$$$ and last exactly $$$K$$$ notes, mod $$$10^9 + 7$$$

2 1 10 0
2 3
0 1

0

3 4 3 0
1 2 3
0 1
1 2
1 0
2 1

8

In the first example, the only way to make a melody is to use a note from instrument $$$0$$$ and then a note from instrument $$$1$$$. After this second note, no further notes can be added to the melody, since no instrument is allowed to follow instrument $$$1$$$. So, there are no melodies of length $$$10$$$.

In the second example, there are two ways to make a melody: use instruments $$$0, 1, 2$$$, in that order, or $$$0, 1, 0$$$, in that order. In the first case, there are $$$1\cdot2\cdot3 = 6$$$ ways to choose the notes, and in the second, there are $$$1\cdot 2\cdot 2 = 2$$$, for a total of $$$8$$$.