Description

有限循环共和国实施了一项独特的法律。根据该法律，永不停机的程序被视为病毒。发布此类程序属于网络犯罪。因此，你希望确保你的软件产品在正常使用下总是会停机。

众所周知，不存在一种算法能够判断任意给定程序在任意给定输入下是否会停机。幸运的是，你的产品基于下面给出的简单计算模型。因此，你可以编写一个程序来判断基于该模型的给定程序在给定输入下最终是否会停机。

产品的计算模型只有一个变量 $x$ 和 $N + 1$ 个状态，编号从 $1$ 到 $N + 1$。变量 $x$ 可以存储任何整数值。状态 $N + 1$ 表示程序已终止。对于每个整数 $i$ （$1 \le i \le N$），程序在状态 $i$ 下的行为由五个整数 $a_i$、$b_i$、$c_i$、$d_i$ 和 $e_i$ 描述（$c_i$ 和 $e_i$ 是状态的索引）。

程序启动时，其状态初始化为 $1$，变量 $x$ 的值初始化为 $x_0$，即程序的输入。当程序处于状态 $i$ （$1 \le i \le N$）时，每一步执行会发生以下情况之一：

• 如果 $x$ 等于 $a_i$，则 $x$ 的值变为 $x + b_i$，程序状态变为 $c_i$；
• 否则，$x$ 的值变为 $x + d_i$，程序状态变为 $e_i$。

当程序状态变为 $N + 1$ 时，程序终止。

你的任务是编写一个程序来判断给定程序在给定输入下最终是否会停机，并且如果停机，计算执行了多少步。初始化不计为一步。

Input Format

输入包含单个测试用例，格式如下。

$$\begin{aligned} &N\ x_0 \\ &a_1\ b_1\ c_1\ d_1\ e_1 \\ &\vdots \\ &a_N\ b_N\ c_N\ d_N\ e_N \end{aligned}$$

第一行包含两个整数 $N$ （$1 \le N \le 10^5$）和 $x_0$ （$-10^{13} \le x_0 \le 10^{13}$）。程序的状态数量为 $N + 1$。$x_0$ 是变量 $x$ 的初始值。接下来的 $N$ 行中，每行包含五个整数 $a_i, b_i, c_i, d_i$ 和 $e_i$，用于确定程序处于状态 $i$ 时的行为。$a_i$、$b_i$ 和 $d_i$ 是介于 $-10^{13}$ 和 $10^{13}$ 之间（含）的整数。$c_i$ 和 $e_i$ 是介于 $1$ 和 $N + 1$ 之间（含）的整数。

Output Format

如果给定程序在给定输入下最终停机，则输出一行一个整数，表示程序终止前执行的步数。由于该数字可能非常大，请输出该数字对 $10^9 + 7$ 取模的结果。

如果程序永不停机，则输出 $-1$。

2 0
5 1 2 1 1
10 1 3 2 2

9

3 1
0 1 4 2 3
1 0 1 1 3
3 -2 2 1 4

-1

3 3
1 -1 2 2 2
1 1 1 -1 3
1 1 4 -2 1

-1

13 3
15 -10 4 4 2
19 0 4 4 3
23 -20 4 4 1
6 1 2 1 5
6 17 3 -1 6
3 2 9 4 7
7 0 9 4 8
11 -5 9 4 6
6 1 7 1 10
6 5 8 -8 11
1 2 11 1 12
6 1 14 2 13
6 -4 11 1 12

26