|
||||||||||
循环图Time Limit: 40000/20000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 588 Accepted Submission(s): 206 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
Sample Output
Source | ||||||||||
|