우주 심연 랠리

치올콥스키 공식에 따르면, 정지 상태에서 속도 $v$까지 로켓을 가속하는 데 필요한 연료의 총량은 다음과 같다.

$m = m_0\left(e^{\frac{v}{u}} - 1\right)$

여기서 $m_0$은 로켓의 빈 질량이고, $u$는 연료의 분사 속도이다. 이 공식은 가속 과정에서 연료 탱크가 완전히 비워지는 경우에만 성립한다.

이 문제에서는 연료 탱크의 용량이 무한하며, $m_0 = 1$, $u = 1$, $e \approx 2$, $e^{\frac{v}{u}} \gg 1$이라고 가정한다. 이 경우 로켓을 속도 $v$까지 가속하는 데 $2^{v}$ 단위의 연료가 든다.

우주 공간에서 랠리가 열린다. 코스는 $V$개의 체크포인트와, 체크포인트를 잇는 $E$개의 양방향 장애물 코스로 이루어진다. 장애물 코스 $k$를 통과하려면 로켓을 속도 $k$까지 가속해야 한다.

모든 체크포인트를 통과하려면 로켓이 완전히 멈춰야 한다. 제동에는 연료가 들지 않는다. 연료 탱크는 체크포인트에서 채울 수 있다.

두 체크포인트를 잇는 장애물 코스는 최대 하나이다. 어떤 장애물 코스도 체크포인트를 자기 자신과 잇지 않는다. 어느 체크포인트에서든 장애물 코스를 따라 다른 모든 체크포인트에 도달할 수 있다.

랠리는 $Q$개의 구간으로 이루어진다. 각 구간에서는 체크포인트 $p$에서 체크포인트 $q$까지 이동해야 한다. 각 구간을 통과하는 데 필요한 최소 연료량을 구한다. 연료량이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

첫 줄에는 공백으로 구분된 정수 세 개가 주어진다. 체크포인트의 수 $V$ ($1 \le V \le 10^5$), 장애물 코스의 수 $E$ ($1 \le E \le 3 \cdot 10^5$), 구간의 수 $Q$ ($1 \le Q \le 10^5$)이다.

다음 $E$개의 줄에는 각각 공백으로 구분된 정수 $a$와 $b$ ($1 \le a \le V$, $1 \le b \le V$)가 주어진다. 이는 체크포인트 $a$와 $b$가 양방향 장애물 코스로 연결되어 있음을 뜻한다. 파일의 $k + 1$번째 줄은 장애물 코스 $k$를 나타낸다.

다음 $Q$개의 줄에는 각각 공백으로 구분된 정수 $p$와 $q$ ($1 \le p \le V$, $1 \le q \le V$)가 주어진다. 각 구간이 시작하고 끝나는 체크포인트이다.

$Q$개의 줄을 출력한다. 각 줄에는 한 구간을 통과하는 데 필요한 최소 연료량을 출력한다. 답은 입력에 주어진 구간의 순서대로 출력한다.