Byteland 国有 $n$ 座城市。任意两座城市之间都有一条双向道路。对于每一条道路，其通行状态要么是允许（开启），要么是禁止（关闭）。在第 0 天，只有 $m$ 条道路是开启的。

每一天（从第 1 天开始），Byteland 政府会选择一条道路。每条道路被选中的概率相同。然后，如果该道路当前是允许通行的，政府就将其关闭；反之，如果该道路当前是禁止通行的，政府就将其开启。

Byteland 政府非常关心城市之间的连通性。政府有 $q$ 个时间段 $[l, r]$，想要知道在这些时间段内，存在某一天使得国家是连通的概率。我们称一个国家是连通的，是指可以从任意一座城市出发，通过一条或多条允许通行的道路到达其他任何城市。

可以证明，所需的概率可以表示为有理数 $P/Q$ 的形式，其中 $P$ 和 $Q$ 互质且 $Q \not\equiv 0 \pmod{10^9 + 7}$。作为 Byteland 最聪明的公民，请你计算这些概率，并以 $P \cdot Q^{-1} \pmod{10^9 + 7}$ 的形式输出。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 5, 0 \le m \le \frac{n(n-1)}{2}$)，分别表示 Byteland 的城市数量和第 0 天允许通行的道路数量。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq 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$ 是对应的概率。

样例

输入 1

3 1
1 2
9
0 0
0 1
0 2
0 3
0 4
1 1
2 2
3 3
4 4

输出 1

0
666666672
666666672
888888896
888888896
666666672
222222224
407407411
469135806

输入 2

2 1
1 2
5
0 0
0 1
1 1
1 1000
0 1000

输出 2

1
1
0
1
1

说明

考虑第一个样例。在第一个请求中，政府没有选择任何道路，且国家从一开始就不连通，因此概率为 0。在第 2 到第 9 个查询中，概率分别为 $2/3, 2/3, 8/9, 8/9, 2/3, 2/9, 20/27$ 和 $20/81$。