Rally in Deep Space

According to the Tsiolkovsky formula, accelerating a rocket from rest to speed $v$ takes this much fuel in total:

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

Here $m_0$ is the empty mass of the rocket and $u$ is the exhaust speed of the fuel. The formula holds only when the fuel tank is emptied during the acceleration.

In this problem, the fuel tank has unlimited capacity, $m_0 = 1$, $u = 1$, $e \approx 2$, and $e^{\frac{v}{u}} \gg 1$. In this case, accelerating the rocket to speed $v$ takes $2^{v}$ units of fuel.

A rally is held in deep space. The course consists of $V$ checkpoints and $E$ two-way obstacle courses that connect the checkpoints. To pass obstacle course number $k$, the rocket must be accelerated to speed $k$.

To pass each checkpoint, the rocket must come to a complete stop. Braking uses no fuel. The fuel tank can be refilled at checkpoints.

Each pair of checkpoints is connected by at most one obstacle course. No obstacle course connects a checkpoint to itself. From any checkpoint, you can reach every other checkpoint by following obstacle courses.

The rally has $Q$ stages. In each stage, the rocket must travel from checkpoint $p$ to checkpoint $q$. Find the minimum fuel needed for each stage. Since fuel costs can be very large, print them modulo $10^9 + 7$.

The first line contains three space-separated integers: the number of checkpoints $V$ ($1 \le V \le 10^5$), the number of obstacle courses $E$ ($1 \le E \le 3 \cdot 10^5$), and the number of stages $Q$ ($1 \le Q \le 10^5$).

Each of the next $E$ lines contains two space-separated integers $a$ and $b$ ($1 \le a \le V$, $1 \le b \le V$), meaning checkpoints $a$ and $b$ are connected by a two-way obstacle course. Line $k + 1$ describes obstacle course $k$.

Each of the next $Q$ lines contains two space-separated integers $p$ and $q$ ($1 \le p \le V$, $1 \le q \le V$), giving the checkpoints where the stage starts and ends.

Print $Q$ lines. On each line, print the minimum fuel needed for one stage. Print the answers in the same order as the stages appear in the input.