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.
hide comments
koushik s:
20180614 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?


Radosav227:
20150407 19:11:13
Fun problem , but there is a problem with the compilation on the SPOJ server.


Red:
20150407 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æ:
20150406 02:28:55
Very nice problem! :) Last edit: 20150406 02:42:47 

PetarV:
20150401 10:59:50
Very nice problem! :) 

Federico LebrÃ³n:
20130511 06:25:11
Are the following two paths the same for Matt?


Edelweiss:
20130510 16:44:22
The Explanation of Example 1 should be "1>2", not "1>3". ^^


Federico LebrÃ³n:
20130510 16:44:22
What are the palm trees used for?

Added by:  SourSpinach 
Date:  20130509 
Time limit:  8s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem 