题目背景

“因为是······他的命令”

题意描述

基地有 $n$ 个房间和 $m$ 条双向通道组成，每条通道经过时需要花费一个定值时间 $c_i$。房间有 $NS$ 个休息室，其余为训练室。

每个训练室负责（耐力，力量，格斗，射击）四个项目之一，训练需要花费一定时间 $t_i$。

每个 $TS$ 个时间单位称作一个周期，一个周期结束时必须位于某个休息室。

必须在 $NR$ 个时间周期之内完成全部项目的训练（次数无关紧要）。

初始时位于一号房间（一定时休息室），可以在任何一个时间周期，任何一个休息室结束训练。

当满足一下条件中任意一个时，两个方案被称为本质不同的：

• 时间周期不同
• 某个周期结束后，两种方案位于不同的休息室
• 存在一个项目，使得在某个周期中，$A$ 方案训练该项目，而 $B$ 方案没有训练该项目。

求本质不同的方案数，由于答案可能很大，输出答案对 $10^9+7$ 取模的余数。

输入格式

第一行四个数 $n,m,TS,NR$，空格分隔，含义见题目。

第二行 $n$ 个数 $TYP_i$，为 $0$ ~ $4$ 之间的整数， $0$ 表示该房间为休息室，否则为训练室，$1$ ~ $4$ 分别对应耐力，力量，格斗，射击训练室。

第三行 $n$ 个数 $T_i$，表示该房间训练所需时间，若为休息室，则 $T_i = 0$。

接下来 $m$ 行，每行 $3$ 个数 $x_i, y_i, c_i$，表示一条双向通道。

输出格式

一个数，表示本质不同的方案对 $10^9+7$ 取模的余数。

样例

5 4 30 3
0 1 2 3 4
0 1 15 15 15
1 2 1
1 3 1
1 4 1
1 5 1

42

$2,3,4$ 号项目训练一个来回需要 $17$ 单位时间，即每个周期只能训练其中的一项，共三个周期，有六种分配方案，而 $1$ 号项目只需 $3$ 单位时间，每个周期都可以训练，但不能都不训练，共 $7$ 中分配方案，相乘共计 $42$ 中分配方案。

数据规模和约定

对于 $20\%$ 的数据, $1 \le n \le 25$，$1 \le m \le 100$，$1 \le NS \le 10$，$1 \le NR \le 100$。

对于 $50\%$ 的数据，$1\le n\le 100$，$1\le m \le 500$，$1\le NS \le 10$。

对于 $100\%$ 的数据，$1 \le n \le 1000$，$1\le m \le 5000$，$1\le NS \le 50$，$1 \le TS \le 10^4$，$1\le NR \le 10^9$，$1 \le T_i , c_i \le 1000$。