도로 연결성

Byteland 나라에는 $n$개의 도시가 있다. 모든 두 도시 사이는 양방향 도로로 연결되어 있다. 각 도로는 통행이 허용(개통)되어 있거나 금지(폐쇄)되어 있다. 0일차에는 $m$개의 도로만 개통되어 있다.

1일차부터 매일 정부는 도로 하나를 고른다. 모든 도로가 뽑힐 확률은 같다. 뽑은 도로의 통행이 허용되어 있으면 정부가 그 도로를 폐쇄하고, 금지되어 있으면 개통한다.

정부는 도시 사이의 통신에 관심이 많다. $q$개의 날짜 구간 $[l, r]$이 주어지며, 각 구간에 대해 그 구간 안의 어느 하루에 나라가 연결되어 있을 확률을 구하려고 한다. 나라가 연결되어 있다는 것은 임의의 두 도시 사이를 허용된 도로 하나 이상으로 이동할 수 있다는 뜻이다.

구하는 확률은 $P/Q$ 꼴의 기약분수로 나타낼 수 있으며, $Q \not\equiv 0 \pmod{10^9 + 7}$이다. 이 값을 계산하여 $P \cdot Q^{-1} \pmod{10^9 + 7}$ 형태로 출력하라.

첫 줄에 두 정수 $n$과 $m$ ($2 \le n \le 5$, $0 \le m \le \frac{n \cdot (n - 1)}{2}$)이 주어진다. 각각 도시의 수와 0일차에 통행이 허용된 도로의 수이다.

이어지는 $m$개의 줄에는 두 정수 $u_i$와 $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$)가 주어지며, $i$번째 개통 도로가 잇는 두 도시를 뜻한다. 개통 도로는 모두 서로 다른 것이 보장된다.

다음 줄에는 질의의 수 $q$ ($1 \le q \le 1000$)가 주어진다.

이어지는 $q$개의 줄에는 두 정수 $l$과 $r$ ($0 \le l \le r \le 10^{15}$)이 주어지며, 정부가 관심을 두는 날짜 구간을 뜻한다.

$q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 질의의 답을 $P \cdot Q^{-1} \pmod{10^9 + 7}$ 형태의 정수 하나로 출력한다. 여기서 $P/Q$는 해당 질의의 확률이다.

첫 번째 예제에서 첫 번째 질의는 정부가 아직 도로를 하나도 고르지 않은 상태이고, 시작 시점에 나라가 연결되어 있지 않으므로 확률은 $0$이다. 두 번째부터 아홉 번째 질의의 확률은 각각 $2/3$, $2/3$, $8/9$, $8/9$, $2/3$, $2/9$, $20/27$, $20/81$이다.