坎格鲁斯普雷被困在了一张循环图里，这张循环图有无数个节点，初始时坎格鲁斯普雷在 $1$ 号节点。

循环图是边存在着一定循环关系的图，循环图里面的边可以用循环周期 $n$ 和 $m$ 对三元组 $(u_i,v_i,w_i)(1 \lt u_i \le n, u_i+1 \le v_i \le 2 \times n, 1 \le w_i \le 10^9$ 表示。每对三元组 $(u_i,v_i,w_i)$ 表示，对于循环图内所有的满足 $s=u_i +k×n ，t=v_i +k×n (k∈N)$ 的点对 $(s,t)$ ，都存在有 $w_i$ 条从点 $s$ 通往点 $t$ 的边。

现在，坎格鲁斯普雷知道了这张循环图的第 $L$ 个节点到第 $R$ 个节点各存在着一个出口，坎格鲁斯普雷需要到达这些节点中的任意一个才能逃出循环图（到达有出口存在的节点后不一定要立刻逃出）。坎格鲁斯普雷想请你帮他算算，他有多少种逃出这张循环图的方式。由于答案可能很大，你需要输出答案对 $10^9 +7$ 取模后的结果。

输入第一行一个整数 $T$ ，表示测试数据组数。 $(1≤T≤10)$

对于每组测试数据，第一行四个整数 $n,m, L, R(1≤n≤100,m≥1,1≤L≤R≤10^{18} )$

接下来 $m$ 行，每行三个整数 $u_i,v_i,w_i$。$(1\le u_i \le n, u_i+1 \le v_i \le 2 \times n, 1\le w_i \le 10^9)$

数据保证在同一组测试数据中，若 $i \neq j$，那么 $u_i = u_j$ 和 $v_i=v_j$ 不同时成立。

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