循环图

Problem Description

坎格鲁斯普雷被困在了一张循环图里，这张循环图有无数个节点，初始时坎格鲁斯普雷在 $1$ 号节点。 循环图是边存在着一定循环关系的图，循环图里面的边可以用循环周期 $n$ 和 $m$ 对三元组 $(u_i,v_i,w_i)$ $(1 \leq u_i \leq n , u_i + 1 \leq v_i \leq 2 \times n,1 \leq w_i \leq 10^9)$ 表示。每对三元组 $(u_i,v_i,w_i)$ 表示，对于循环图内所有的满足 $s = u_i + k \times n$ ， $t = v_i + k \times n$ $( k \in N )$ 的点对 $(s,t)$ ，都存在有 $w_i$ 条从点 $s$ 通往点 $t$ 的边。 现在，坎格鲁斯普雷知道了这张循环图的第 $L$ 个节点到第 $R$ 个节点各存在着一个出口，坎格鲁斯普雷需要到达这些节点中的任意一个才能逃出循环图（到达有出口存在的节点后不一定要立刻逃出）。坎格鲁斯普雷想请你帮他算算，他有多少种逃出这张循环图的方式。由于答案可能很大，你需要输出答案对 $10^9+7$ 取模后的结果。

Input

输入第一行一个整数 $T$ ，表示测试数据组数。 $(1 \leq T \leq 10)$ 对于每组测试数据，第一行四个整数 $n$ ， $m$ ， $L$ ， $R$ 。 $(1 \leq n \leq 100 , m \geq 1 , 1 \leq L \leq R \leq 10^{18})$ 接下来 $m$ 行，每行三个整数 $u_i$ ，$v_i$ ，$w_i$ 。 $(1 \leq u_i \leq n , u_i + 1 \leq v_i \leq 2 \times n,1 \leq w_i \leq 10^9)$ 数据保证在同一组测试数据中，若 $i \neq j$ ，那么 $u_i = u_j$ 和 $v_i = v_j$ 不同时成立。

Output

对于每组测试数据，输出一行一个整数表示答案。每两组测试数据之间的答案需换行。

Sample Input

2
3 4 5 6
1 2 1
1 3 1
3 4 1
2 5 1
5 8 998244353 1000000007
1 2 114514
1 4 1919810
2 3 999999999
3 5 111111111
4 5 1000000000
1 10 123456789
5 6 987654321
3 9 888888888

Sample Output

3
18719743

Source

2024“钉耙编程”中国大学生算法设计超级联赛（7）