题目描述

在一片神秘的魔法森林中，有N个魔法节点，由 M条有向魔法路径相连。这些路径不存在自环和重复路径。 位于森林边缘的1号魔法节点是进入森林的入口，而森林深处的N号魔法节点则是出口。

每条魔法路径都带有一个魔力值，这个魔力值代表着探险家沿着这条路径行走时，所消耗的魔力。年轻的 探险家艾丽每天都会进入魔法森林探险，她总是从1号节点进入，从 N号节点走出。

艾丽对新奇的探险充满热情，她不希望连续两天的探险路线完全相同。同时，艾丽携带的魔力水晶所储存 的魔力有限，她知道从1号节点到 N号节点消耗魔力最少的路线（即最短魔力消耗路径）所花费的魔力值为 d。因此，艾丽只会选择消耗魔力值不超过 d+K的探险路线。

艾丽想知道，满足条件的探险路线一共有多少条。由于路线数量可能非常庞大，所以答案需要对P取模。如果 存在无数条满足条件的路线，那就意味着这片魔法森林隐藏着特殊的魔力循环，此时需要告知艾丽结果为 -1。 你能帮助艾丽解决这个难题吗？

【输入格式】

第一行包含一个整数T, 代表数据组数。

接下来T组数据，对于每组数据：

第一行包含四个整数 N,M,K,P,每两个整数之间用一个空格隔开。

接下来M行，每行三个整数a[i],b[i],c[i],代表编号为a[i],b[i]的点之间有一条权值为c[i]的有 向边，每两个整数之间用一个空格隔开。

【输出格式】

输出文件包含T行，每行一个整数代表答案。

输入样例

2

5 7 2 10 1 2 1

2 4 0

4 5 2

2 3 2

3 4 1

3 5 2

1 5 3

2 2 0 10 1 2 0

2 1 0

输出样例

3

-1

数据范围

对于100%的数据, 1≤P≤10^9,1≤a[i],b[i]≤N,0≤c[i]≤1000。数据保证：至少存在一条合法的路线。