F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

循环图

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
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
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-10 07:40:12, Gzip enabled