비가역 반응

인생은 덧없다. 어떤 일은 되돌릴 수 없다. 이런 점에서 화학 반응 네트워크는 인생과 닮아 있다.

간결한 설명을 위해 화학 반응 네트워크를 다음과 같이 모델링한다. 화학 반응 네트워크에는 $N$개의 상태가 있다. 반응은 상태 $S$에서 시작한다. $M$개의 서로 다른 상태 쌍 ($u_i$, $v_i$)에는 $u_i$에서 $v_i$로 전이할 수 있다는 관계가 있다. 각 시간 단위마다, 현재 상태에서 전이할 수 있는 상태가 하나라도 있으면 다른 상태로 전이한다. 그런 상태가 없으면 현재 상태는 변하지 않는다. 현재 상태에서 전이할 수 있는 상태가 둘 이상이면, 다음 상태는 그중에서 균등한 확률로 선택된다.

화학 반응 네트워크 실험에서는 현재 상태가 변하지 않을 때 실험을 중단한다. 또한, 전이를 반복하다 보면 전이를 반복해서 $S$로 돌아갈 수 없는 상태에 도달할 수도 있다. 이 경우에도 실험을 중단한다. 생물정보학 연구자로서 해야 할 일은 실험이 중단될 때까지 걸리는 기대 시간을 계산하는 프로그램을 작성하는 것이다. 기대 시간이 무한이면 대신 $-1$을 출력한다.

실험 종료 조건을 더 정확히 설명하면 다음과 같다. 현재 상태에서 전이할 수 있는 상태가 없으면 즉시 실험을 중단한다. 그렇지 않고, 전이를 0번 이상 반복해서 현재 상태에서 $S$로 돌아갈 수 있으면 실험을 중단하지 않는다. 즉, 이 경우 상태 $S$ 자체는 항상 $S$로 돌아갈 수 있는 상태로 간주한다.

입력은 아래 형식의 단일 테스트 케이스로 이루어진다.

$N$ $M$ $S$

$u_1$ $v_1$

$\vdots$

$u_M$ $v_M$

첫째 줄에는 세 정수 $N$ ($2 \le N \le 200$), $M$ ($1 \le M \le \min{(N(N-1)1000)}$), $S$ ($1 \le S \le N$)가 주어진다. $N$은 화학 반응 네트워크의 상태 수다. $M$은 상태 간 전이의 수다. $S$는 초기 상태다. 다음 $M$개의 줄 중 $i$번째 줄은 $i$번째 전이를 나타내며, 상태 $u_i$에서 $v_i$로 전이할 수 있다는 뜻이다 ($1 \le u_i, v_i \le N$, $u_i \ne v_i$). $v_i$에서 $u_i$로 전이할 수 있다는 뜻은 아니다. 쌍 $u_i$와 $v_i$는 서로 다르다는 것이 보장된다. 즉, $1 \le i < j \le M$에 대해 $u_i \ne u_j$이거나 $v_i \ne v_j$이다.

초기 상태 $S$로 돌아갈 수 없는 상태 중 하나에 도달할 때까지 걸리는 기대 시간을 출력한다. 기대 시간은 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다. 더 정확히는, 기대 시간이 유한하면 기약분수 $b/a$로 나타낼 수 있고, $ax \equiv b \bmod {10^9 + 7}$을 만족하는 최소 음이 아닌 정수 $x$를 출력해야 한다. 주어진 입력에 대해 그러한 $x$가 존재한다고 가정해도 된다.

기대 시간이 무한이면 대신 $-1$을 출력한다.