정지 문제

유한 루프 공화국에서는 독특한 법률이 시행된다. 이 법에 따르면 영원히 멈추지 않는 프로그램은 바이러스로 간주된다. 이런 프로그램을 배포하면 사이버 범죄가 된다. 따라서 소프트웨어 제품은 정상적으로 사용될 때 항상 멈추도록 만들어야 한다.

임의의 프로그램이 임의의 입력에 대해 멈추는지 판정하는 알고리즘은 존재하지 않는다는 것은 잘 알려져 있다. 다행히 제품은 아래의 단순한 계산 모델을 기반으로 한다. 따라서 이 모델을 따르는 주어진 프로그램이 주어진 입력에 대해 결국 멈추는지 판정하는 프로그램을 작성할 수 있다.

계산 모델은 변수 $x$ 하나와 1번부터 $N + 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 x0
a1 b1 c1 d1 e1
.
.
.
aN bN cN dN eN

첫 줄에는 정수 $N$ ($1 \le N \le 10^5$)과 $x_0$ ($-10^{13} \le x_0 \le 10^{13}$)이 주어진다. 프로그램에는 $N + 1$개의 상태가 있다. 다음 $N$개의 줄에는 상태 $i$에서의 동작을 정하는 정수 다섯 개 $a_i$, $b_i$, $c_i$, $d_i$, $e_i$가 주어진다. $a_i$, $b_i$, $d_i$는 $-10^{13}$ 이상 $10^{13}$ 이하이고, $c_i$와 $e_i$는 1 이상 $N + 1$ 이하이다.

주어진 입력에 대해 프로그램이 결국 멈추면, 종료될 때까지 실행된 단계 수를 한 줄에 정수 하나로 출력하라. 값이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

프로그램이 영원히 멈추지 않으면 $-1$을 출력한다.