MATT - Matts Trip

Matt finds himself in a desert with $N$ ($2 \leq N \leq 10$) oases, each of which may have food, water, and/or a palm tree. If oasis $i$ has food, then $F_i=1$ - otherwise, $F_i=0$. Similarly, $W_i=1$ if and only if oasis $i$ has water, and $P_i=1$ if and only if it has a palm tree. These 3 values are completely independent of one another.

Some pairs of these oases are connected by desert paths, which each take 1 hour to traverse. There are $M$ ($0 \leq M \leq 45$) such paths, with path $i$ connecting distinct oases $A_i$ and $B_i$ in both directions ($1 \leq A_i,B_i \leq N$). No pair of oases is directly connected by more than one path, and it's not guaranteed that all oases are connected by some system of paths.

Matt starts at an oasis $S$, and wants to end up at a different oasis $E$ ($1 \leq S,E \leq N$).

Both of these oases are quite nice - it's guaranteed that $F_S=W_S=P_S=F_E=W_E=P_E=1$.

Since he's in a hurry to get out of the desert, he wants to travel there in at most $H$ ($1 \leq H \leq 10^9$) hours.

However, he can only survive for up to $MF$ hours at a time without food, and up to $MW$ hours at a time without water ($1 \leq MF,MW \leq 4$). For example, if $MF=1$ and $MW=2$, then every single oasis he visits along the way must have food (as he would otherwise spend more than 1 hour without it), and he cannot visit 2 or more oases without water in a row.

Since Matt is a computer scientist, before actually going anywhere, he's interested in the number of different paths he can take that will get him from oasis $S$ to oasis $E$ alive in at most $H$ hours.

Note that there may be no such paths.

Being a computer scientist, he of course only cares about this number modulo ($10^9+7$).

Input

Line $1$: 7 integers, $N$, $M$, $H$, $S$, $E$, $MF$, and $MW$

Next $N$ lines: 3 integers, $F_i$, $W_i$, and $P_i$, for $i = 1..N$

Next $M$ lines: 2 integers, $A_i$ and $B_i$, for $i = 1..M$

Output

1 integer, the number of different valid paths, modulo ($10^9+7$)

Example 1

Input:

3 3 3 1 2 1 4

1 1 1

1 1 1

0 1 0

1 2

2 3

1 3

Output:
2
Explanation:

The two possible paths, described in terms of oases visited, are $1 \rightarrow 2$ and $1 \rightarrow 2 \rightarrow 1 \rightarrow 2$. Matt can never go to oasis 3, as it doesn't contain food, which he can't survive without for more than 1 hour. The path $1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 2$ is not valid, as it would take 5 hours rather than at most 3.

Note that oasis 3 is the only oasis without a palm tree.

Example 2

Input:

5 5 3 3 2 3 2

1 0 0

1 1 1

1 1 1

0 0 1

0 1 0

1 2

1 3

1 4

3 4

4 2

Output:
2
Explanation:

The two possible paths are $3 \rightarrow 1 \rightarrow 2$ and $3 \rightarrow 4 \rightarrow 2$.

This time, oases 1 and 5 are lacking in palm trees. koushik s: 2018-06-14 09:12:56 if start and end are at the same oasis and not moving a single step is also considered as a valid path? RE: Yes, that counts as a path which takes 0 time. Last edit: 2018-12-02 10:47:21 Radosav227: 2015-04-07 19:11:13 Fun problem , but there is a problem with the compilation on the SPOJ server. I have written my solution in c# and ran it on ideone with your test cases and it is working fine there, it is also working on all of my machines , and i'm not even close to any of the limits, yet when i run it on the SPOJ server it get a SIGABRT error. Any ideas on how i can fix this? Red: 2015-04-07 14:42:07 I am trying to submit solution, and my program is working fine, but when i submit it outputs runtime error (SIGSEGV), i checked there's no overflow, not accessing any thing i did not put in memory. I tried to register on forum but it won't send mi activation mail that's why I'm posting this here. Can anyone tell me what should I do? Dragan Markoviæ: 2015-04-06 02:28:55 Very nice problem! :) Last edit: 2015-04-06 02:42:47 PetarV: 2015-04-01 10:59:50 Very nice problem! :) Federico LebrÃ³n: 2013-05-11 06:25:11 Are the following two paths the same for Matt? {A -> B -> A -> B -> C, A -> B -> C} (That is, does Matt want walks, or paths? Does he count only simple paths, or with cycles as well?) RE: Same as in sample 1, those are different paths, and paths with cycles are valid. RE: Thanks :) AC, thanks a lot for this problem! I enjoyed it. RE: Great, no problem! Last edit: 2013-05-13 12:38:05 Edelweiss: 2013-05-10 16:44:22 The Explanation of Example 1 should be "1->2", not "1->3". ^^ RE: Oops, thanks - it's been fixed. Last edit: 2013-05-10 16:44:54 Federico LebrÃ³n: 2013-05-10 16:44:22 What are the palm trees used for? RE: They look pretty nice. Last edit: 2013-05-10 01:39:54