题目描述

有一张 $n$ 个点的无向图，初始它的形态为给定的图 $G_0$。

接下来的 $10^{15}$ 个时刻内，每个时刻图中都会随机有一个点对 $(u,v)$ 之间的连边状态反转，即有边 $\to$ 没有边，没有边 $\to$ 有边。设 $G_i$ 表示第 $i$ 个时刻的这张图。那么一共有 $(\frac{n(n-1)}{2})^{10^{15}}$ 种可能的图序列，它们的概率都是一样的。

现在你需要回答 $Q$ 次询问，每次询问会给出正整数 $L,R$，你需要求出以下事件发生的概率：

• 存在某个 $L\le i\le R$，使得 $G_i$ 是连通图。

答案对 $10^9+7$ 取模。

输入格式

第一行两个正整数 $n,m$ 表示图的点数，以及初始时的边数。

接下来 $m$ 行每行两个正整数 $u,v$ 表示 $G_0$ 中的一条边。

接下来一个正整数 $Q$ 表示询问次数。

接下来 $Q$ 行每行两个正整数 $L,R$ 表示一次询问。

输出格式

对于每组询问，输出一行一个整数表示答案。

样例 $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

样例 $1$ 解释

所有询问取模前的真实答案分别为：$0,\frac{2}{3},\frac{2}{3},\frac{8}{9},\frac{8}{9},\frac{2}{3},\frac{2}{9},\frac{20}{27},\frac{20}{81}$。

样例 $2$ 输入

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

样例 $2$ 输出

1
1
0
1
1

大样例

大样例分别符合测试点 2,4,11,14,18,23 的约束。

测试点约束

对于所有数据，$2\le n\le 5,1\le Q\le 1000,0\le L\le R\le 10^{15}$。