SP14886 MATT - Matts Trip

马特发现自己身处一片沙漠，这里有 $N$ 个绿洲（$2 \leq N \leq 10$）。每个绿洲可能拥有食物、水源或者棕榈树。如果某个绿洲 $i$ 拥有食物，那么 $F_i=1$，否则 $F_i=0$；$W_i=1$ 表示绿洲有水，否则 $W_i=0$；$P_i=1$ 表示绿洲有棕榈树，否则 $P_i=0$。这些属性彼此独立。 绿洲之间通过沙漠小径相连，走完每条小径需要1小时。共有 $M$ 条小径（$0 \leq M \leq 45$），每条小径双向连接两座不同的绿洲 $A_i$ 和 $B_i$（$1 \leq A_i, B_i \leq N$）。一个绿洲对之间最多只有一条直接相连的小径，并且不保证所有绿洲可以通过这些小径互相连接。 马特从绿洲 $S$ 出发，目标是到达另一个绿洲 $E$（$1 \leq S, E \leq N$）。这两个绿洲都很优越，保证有食物、水和棕榈树，即 $F_S=W_S=P_S=F_E=W_E=P_E=1$。 由于急于离开沙漠，马特希望路径不超过 $H$ 小时（$1 \leq H \leq 10^9$）。 然而，他每次在没有食物和水的情况下最多只能生存 $MF$ 小时和 $MW$ 小时（$1 \leq MF, MW \leq 4$）。比如，如果 $MF=1$ 且 $MW=2$，那么他路过的每个绿洲都必须有食物，而不能连续在两个或以上没有水的绿洲之间行走。 马特是一个计算机科学家，在真正出发前，他想要计算从绿洲 $S$ 到绿洲 $E$ 的不同路径数量，这些路径需在规定时间内确保他能够存活。 请注意，可能没有任何符合条件的路径。 作为一个计算机科学家，他只关心这个数量对 $10^9 + 7$ 取余的结果。

第一行：7个整数，分别是 $N$，$M$，$H$，$S$，$E$，$MF$ 和 $MW$。 接下来 $N$ 行：每行三个整数，表示第 $i$ 个绿洲的 $F_i$，$W_i$，$P_i$。 接下来 $M$ 行：每行两个整数，表示第 $i$ 条小径连接的绿洲 $A_i$ 和 $B_i$。

输出一个整数，表示符合要求的不同路径数量，对 $10^9 + 7$ 取模的结果。 **本翻译由 AI 自动生成**