A. 阳光运动

内存限制：512 MiB 时间限制：4000 ms 标准输入输出

题目类型：传统评测方式：文本比较

转到题库提交记录返回比赛

在偌大的 Z 大，拥有一辆自行车作为代步工具是必须的……

是一个刚刚进入校园的新生，这天，她装好了自己的新车，从自己的宿舍楼出发，准备游览这片未知的校园。早在报道日，她就领到一个手绘版的校园地图，上面标志着个她想要去参观的地点，校园的道路都是双向的，为了让交通更加便利，两个地点之间常常有不止一条道路。想从学校出发，经过所有景点至少一次并最终回到宿舍休息。

想要自己骑得尽兴，但是又不希望自己太累，所以她想控制自己的路程在之间。

想知道自己骑行方案的数量。两种方案不同，当且仅当它们经过道路的数量不同或顺序不同。

第一行四个整数。

以下行，每行三个整数，表示号目标地点和号目标地点之间有一条长为的双向道路。如果或为，则表示寝室和目标地点之间的双向道路。

一行一个整数，方案数。由于方案数可能很大，你只需要输出它对取模的值即可。

样例输入 1

1 2 3 4
0 1 1
0 1 2

样例输出 1

样例解释 1

条路径分别为：

0 -(1)-> 1 -(2)-> 0;
0 -(2)-> 1 -(1)-> 0;
0 -(2)-> 1 -(2)-> 0;
0 -(1)-> 1 -(1)-> 0 -(1)-> 1 -(1)-> 0.

样例输入 2

样例输出 2

样例解释 2

条路径分别为：

0 -> 1 -> 3 -> 2 -> 0, L = 10;
0 -> 2 -> 3 -> 1 -> 0, L = 10;
0 -> 1 -> 2 -> 3 -> 1 -> 0, L = 10;
0 -> 1 -> 3 -> 1 -> 2 -> 0, L = 10;
0 -> 1 -> 3 -> 2 -> 1 -> 0, L = 10;
0 -> 2 -> 1 -> 3 -> 1 -> 0, L = 10;
0 -> 1 -> 2 -> 1 -> 3 -> 1 -> 0, L = 10;
0 -> 1 -> 3 -> 1 -> 2 -> 1 -> 0, L = 10.

样例输入 3

5 10 50 100
0 1 5
0 2 7
0 3 4
1 3 6
1 4 4
2 3 7
2 4 7
3 4 4
1 5 6
4 5 9

样例输出 3

606168943

对于前的数据，；

对于前的数据，，保证答案取模前不会超过；

对于全部数据，

题目描述

输入格式

输出格式

样例