坎格鲁斯普雷被困在了一张循环图里，这张循环图有无数个节点，初始时坎格鲁斯普雷在 1 号节点。
循环图是边存在着一定循环关系的图，循环图里面的边可以用循环周期 n 和 m 对三元组 (ui,vi,wi)1≤ui≤n,ui+1≤vi≤2×n,1≤wi≤109) 表示。每对三元组 (ui,vi,wi) 表示，对于循环图内所有的满足 s=ui+k×n ， t=vi+k×n (k∈N)的点对 (s,t) ，都存在有 wi 条从点 s 通往点 t 的边。
现在，坎格鲁斯普雷知道了这张循环图的第 LL个节点到第 R 个节点各存在着一个出口，坎格鲁斯普雷需要到达这些节点中的任意一个才能逃出循环图（到达有出口存在的节点后不一定要立刻逃出）。坎格鲁斯普雷想请你帮他算算，他有多少种逃出这张循环图的方式。由于答案可能很大，你需要输出答案对 109+7 取模后的结果。
输入第一行一个整数 T ，表示测试数据组数。 (1≤T≤10)
对于每组测试数据，第一行四个整数 n ， m ， L ， R 。 (1≤n≤100,m≥1,1≤L≤R≤1018)
接下来 m 行，每行三个整数ui ，vi ，wi 。(1≤ui≤n,ui+1≤vi≤2×n,1≤wi≤109)
数据保证在同一组测试数据中，若 i≠j，那么ui=uj 和 vi=vj 不同时成立。
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 8888888883
18719743