Halting Problem

In the Republic of Finite Loop, a unique law is enforced. Under the law, programs that never halt are regarded as viruses. Releasing such a program is a cybercrime. So, you want to make sure that your software products always halt under their normal use.

It is widely known that there is no algorithm that can determine whether an arbitrary program halts for an arbitrary input. Fortunately, your products are based on a simple computation model given below. So, you can write a program that tells whether a given program based on the model will eventually halt for a given input.

The computation model has one variable $x$ and $N + 1$ states, numbered 1 through $N + 1$. The variable $x$ can store any integer value. State $N + 1$ means that the program has terminated. For each integer $i$ ($1 \le i \le N$), the behavior of the program in state $i$ is described by five integers $a_i$, $b_i$, $c_i$, $d_i$, and $e_i$. Here $c_i$ and $e_i$ are indices of states.

When the program starts, its state is set to 1, and $x$ is set to $x_0$, the input to the program. When the program is in state $i$ ($1 \le i \le N$), one of the following happens in one execution step:

• If $x$ is equal to $a_i$, the value of $x$ changes to $x + b_i$ and the program state becomes $c_i$.
• Otherwise, the value of $x$ changes to $x + d_i$ and the program state becomes $e_i$.

The program terminates when its state becomes $N + 1$.

Write a program that determines whether a given program eventually halts for a given input. If it halts, compute how many steps it executes. The initialization is not counted as a step.

The input consists of a single test case in the following format.

N x0
a1 b1 c1 d1 e1
.
.
.
aN bN cN dN eN

The first line contains two integers $N$ ($1 \le N \le 10^5$) and $x_0$ ($-10^{13} \le x_0 \le 10^{13}$). The program has $N + 1$ states. Each of the next $N$ lines contains five integers $a_i$, $b_i$, $c_i$, $d_i$, and $e_i$ that determine the behavior of the program in state $i$. The integers $a_i$, $b_i$, and $d_i$ are between $-10^{13}$ and $10^{13}$ inclusive, and $c_i$ and $e_i$ are between 1 and $N + 1$ inclusive.

If the program eventually halts for the given input, output a single integer on a line: the number of steps executed until the program terminates. Since the number may be very large, output it modulo $10^9 + 7$.

Output $-1$ if the program never halts.