Often, when Aditya writes problems, he gets caught up in making sure that his solution is valid using a series of proofs. He has $n$ different propositions to consider, with labels from $1$ to $n$. He has $m$ implications proved already, where an implication is defined as a pair $(u, v)$, which means that if proposition $u$ is true, then proposition $v$ is also true. Note that you can combine implications to create new implications; for example if you have $(u, v)$ and $(v, w)$, then you can also create the implication $(u, w)$. Aditya's goal is to construct all possible implications between the $n$ propositions, but he recognizes that this might take significant time. Instead, he will pick a starting proposition, $s$, and you must find the number of new implications involving $s$ (of the form $(s, u)$ or $(u, s)$ for arbitrary implication $u eq.not s$) that are not already proved by the $m$ implications Aditya already has.
The first line will consist of 3 space-separated integers $n, m, s$ ($1 <= s <= n <= 10^5$, $0 <= m <= 2 dot.op 10^5$) giving the number of propositions, number of already proved implications, and starting proposition. The next $m$ lines will consist of two space-separated integers $u_i, v_i$ ($1 <= u_i, v_i <= n$), which indicates that Aditya has already proved the implication $(u_i, v_i)$.
Output the number of implications involving $s$ that Aditya has not already proven given the $m$ implications he has.
In the first case, all possible implications can already be proved. In the second case, the unproved implications involving $1$ are $(1, 3)$ and $(3, 1)$.
## Input
The first line will consist of 3 space-separated integers $n, m, s$ ($1 <= s <= n <= 10^5$, $0 <= m <= 2 dot.op 10^5$) giving the number of propositions, number of already proved implications, and starting proposition. The next $m$ lines will consist of two space-separated integers $u_i, v_i$ ($1 <= u_i, v_i <= n$), which indicates that Aditya has already proved the implication $(u_i, v_i)$.
## Output
Output the number of implications involving $s$ that Aditya has not already proven given the $m$ implications he has.
[samples]
## Note
In the first case, all possible implications can already be proved. In the second case, the unproved implications involving $1$ are $(1, 3)$ and $(3, 1)$.
**Definitions**
Let $ n \in \mathbb{N} $ be given in binary representation, with $ 0 \leq n < 2^{3000} $.
Let $ c \in \mathbb{Z} $ be given in decimal, with $ 0 \leq c \leq 10^9 $.
Define the sequence $ a_n $ recursively by:
$$
a_0 = 1, \quad a_n = c \cdot \max_{0 \leq i < n} (a_{n \& i}) \quad \text{for } n \geq 1,
$$
where $ \& $ denotes bitwise AND.
**Constraints**
1. $ n $ is given as a binary string of length at most 3000.
2. $ 0 \leq c \leq 10^9 $.
**Objective**
Compute:
$$
\left( \sum_{i=0}^n a_i \right) \bmod (10^9 + 7)
$$