在有限循环共和国（Republic of Finite Loop）中，有一条独特的法律：永不停止的程序被视为病毒。发布此类程序属于网络犯罪。因此，你需要确保你的软件产品在正常使用下总是会停止。

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

该产品的计算模型只有一个变量 $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$ 时，程序终止。

你的任务是编写一个程序，判断给定的程序对于给定的输入是否最终会停止；如果会停止，计算执行了多少步。初始化不计入步数。

输入格式

第一行包含两个整数 $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$ 之间的整数。

输出格式

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

如果程序永远不会停止，输出 $-1$。

样例

样例输入 1

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

样例输出 1

9

样例输入 2

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

样例输出 2

-1

样例输入 3

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

样例输出 3

-1