题目描述

南锡曾以其新艺术运动街区、朗姆巴巴蛋糕和贤明的国王斯坦尼斯瓦夫·莱什琴斯基（这位被废黜的波兰国王在 18 世纪为这座城市留下了华美繁复的建筑中心）而闻名。

但在 2013 年，南锡重新发现了它的文艺复兴时期历史。从美术馆到温泉浴场再到植物园，整个夏天全城到处都是活动和展览。现在轮到我去探索老城区的文艺复兴遗迹，以及查理三世公爵的乌托邦式城市规划，那时南锡还是一个强大的独立公国的首都，地处北欧和南欧的交汇处。

如今，新老城区已无缝衔接。1588 年规划的新城（Ville Neuve）仍然是该市的商业中心，遍布商店和银行，原本计划建大教堂的广场附近的街道两旁，食品市场鳞次栉比。

今年秋天，我有幸在新城度过一个长达数月的假期。每日的沉思总是伴随着早餐和香甜柔软的法棍面包。让法棍更美味的不是乐芝牛奶酪，而是我买到它的地方。但是，编写计算机程序的人为什么如此关心一条街上的食品市场数量呢？我确实给这条街上供应法棍面包的食品市场贴上了从 $1$ 到 $n$ 的标签。

每当晨曦初露，我便带上几枚一欧元硬币，计划去逛几个连续的食品市场。无论风雨，每个食品市场总是以固定价格提供固定数量的法棍面包。两个不同的市场可能不同：它们每日供应的法棍数量和价格各不相同。

早起的鸟儿有虫吃。由于不必担心其他顾客，有足够的钱我就可以自由地买光一个市场里的所有法棍，或者看也不看直接去下一家。

可是，像你这样的人又何必如此关心我购买法棍的不同方式有多少种呢？他们甚至反复向我确认，我可以一文不花而挨饿，也可以花掉我带的任意金额。正如理论家们在类似背包的问题中常说的那样，如果某些市场上购买的法棍数量不同，那么两种购买法棍的方式就视为不同。

像你这样追求高效率的人，一旦确认了我每天所带的金额和我的访问计划，就会试图告诉我方案的数量。而像我这样随性的人，尽管已经为所有日子制定了一长串计划，却决定在收到你对某一天的答复后，再为下一天制定新的计划。我用 $lastans$ 表示你答复中的数字，并在新城的第一天之前将其设为零。

某一天，我查看原先计划中的内容，记 $l'$ 和 $r'$ 为我决定访问的第一个和最后一个食品市场的编号，记 $c$ 为我决定携带的一欧元硬币的数量。一个类似加密的变换

$$l = \min\{((l' + lastans) \bmod n) + 1, ((r' + lastans) \bmod n) + 1\}$$

和

$$r = \max\{((l' + lastans) \bmod n) + 1, ((r' + lastans) \bmod n) + 1\}$$

向我展示了一个新的计划，其中 $\min\{x, y\}$ 和 $\max\{x, y\}$ 分别表示 $x$ 和 $y$ 的最小值和最大值，而这就是我在今天早上执行的内容。你需要告诉我你为这一天计算出的数字，我会将 $lastans$ 设为你的答复对 $(10^9 + 7)$ 取模的结果。

输入格式

输入包含多组测试数据，第一行包含一个正整数 $T$，表示测试数据的组数，最多不超过 $1000$。

对于每组测试数据，第一行包含两个整数 $n$ 和 $m$，分别表示街道上食品市场的数量和我在新城计划停留的总天数，其中 $1 \le n, m \le 10000$。

接下来的 $n$ 行，每行描述一个食品市场。其中第 $i$ 行包含两个整数 $a_i$ 和 $b_i$，分别表示第 $i$ 个食品市场供应的法棍面包数量和它的欧元单价，满足 $1 \le a_i, b_i \le 1000$。

接下来的 $m$ 行，每行包含三个整数 $l', r'$ 和 $c$，描述我某一天制定的原始计划，其中 $1 \le l' \le r' \le n$，$1 \le c \le 1000$。

我们保证满足 $n > 100$ 或 $m > 100$ 的测试数据不超过 $10$ 组。

输出格式

对于每组测试数据，首先在一行中输出 "Case #x:"（不含引号），其中 $x$ 是测试数据的编号，从 $1$ 开始。

然后对于每一天，在一行中输出一个整数，表示这一天购买法棍面包的不同方案数，结果对素数 $(10^9 + 7)$ 取模。

1
3 3
1 1
1 2
1 3
1 3 1
1 3 2
1 3 3

Case #1:
2
3
4

提示

在样例中，第一天我只带了一枚硬币，访问第一个市场和第二个市场。因此我可以什么都不买，或者在第一个市场买一个法棍。第二天，我带了两枚硬币访问所有市场，因此我可以什么都不买，或者在前两个市场中的任意一个买一个法棍。最后一天，我再次访问前两个市场，但身上带了三枚硬币。这样我就有四种不同的购买法棍的方式，不过在三天的购物之后，我实在太累了，就不把它们一一列举了。

翻译由 DeepSeek V4 Pro 完成