Irreversible Reactions

Life is ephemeral. What is done sometimes cannot be undone. In this respect, chemical reaction networks resemble life.

For brevity, we model a chemical reaction network as follows. There are $N$ states in a chemical reaction network. The reaction starts at state $S$. $M$ distinct pairs ($u_i$, $v_i$) of states have a relation such that $u_i$ can be transitioned to $v_i$. For each unit of time, a state is transitioned to other states if there is at least one state that can be transitioned from it. If there are no such states, the state does not change. If there are two or more states to which the current state can be transitioned, the next state is selected uniformly at random from these states.

In an experiment on the chemical reaction network, we stop the experiment when the current state does not change. In addition, after transitions, it might reach a state from which it is impossible to return to $S$ by repeating transitions. In such cases we also stop the experiment. Your task as a bioinformatics researcher is to write a program to compute the expected time until we stop the experiment. If the expected time is infinite, output $-1$ instead.

A more precise description of the experiment termination criteria is the following. If there are no states that can be transitioned from the current state, we stop the experiment immediately. Otherwise, the experiment does not stop if it is possible to return to $S$ from the current state by repeating zero or more transitions. In other words, the state $S$ itself is always considered as a state that can return to $S$ in this case.

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

$N$ $M$ $S$

$u_1$ $v_1$

$\vdots$

$u_M$ $v_M$

The first line contains three integers $N$ ($2 \le N \le 200$), $M$ ($1 \le M \le \min{(N(N-1)1000)}$), $S$ ($1 \le S \le N$). $N$ is the number of states in a chemical reaction network. $M$ is the number of transitions between states. $S$ is the initial state. The $i$-th of the following $M$ lines represents the $i$-th transition, which means a state $u_i$ can be transitioned to $v_i$ ($1 \le u_i, v_i \le N$, $u_i \ne v_i$). Note that it does not necessarily imply $v_i$ can be transitioned to $u_i$. It is guaranteed that the pairs $u_i$ and $v_i$ are distinct. That is, for $1 \le i < j \le M$, either $u_i \ne u_j$ or $v_i \ne v_j$ holds.

Output the expected time to reach one of the states from which it is impossible to return to the initial state $S$. The expected time can be huge, thus output the expected time modulo $10^9 + 7$. More precisely, if it is finite, the expected time can be represented as an irreducible fraction $b/a$, and you should output the minimum non-negative integer $x$ which satisfies $ax \equiv b \bmod {10^9 + 7}$. You may assume that such $x$ exists for the given input.

If the expected time is infinite, output $-1$ instead.