SP14886 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 $ ).

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 $

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