我们发现，通过每个环的合法路径数都有两种。设从 $x$ 到 $y$ 的路径上有 $d$ 个环，那么答案就是 $2^d$。
问题转化为求两点路径间有多少个环。
我们考虑缩边双。由于题目保证图是一个点仙人掌，因此缩完图之后一定是一棵树。此时我们只需要求两点的树上距离即可。
用 LCA 维护一下就可以了。
时间复杂度 $O(n+m+q\log n)$。
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
int n, m, q;
int head[100005];
int u[1000005], v[1000005], nxt[1000005];
int low[100005], dfn[100005];
bool cut[1000005];
int dcc[100005], size[100005];
int tot = 1, cnt, lza;
vector<int> a[100005];
int f[100005], dep[100005];
int nmsl[100005], son[100005];
int top[100005];
int len[100005];
void add(int x, int y) {
tot++;
u[tot] = x; v[tot] = y;
nxt[tot] = head[x]; head[x] = tot;
}
void dfs(int ed, int x) {
low[x] = dfn[x] = ++cnt;
for (int i = head[x]; i; i = nxt[i]) {
int y = v[i];
if (!dfn[y]) {
dfs(i, y); low[x] = min(low[x], low[y]);
if (dfn[x] < low[y]) cut[i] = cut[i ^ 1] = 1;
} else if (i != (ed ^ 1)) low[x] = min(low[x], dfn[y]);
}
}
void dfs2(int x, int cnt) {
dcc[x] = cnt; size[cnt]++;
for (int i = head[x]; i; i = nxt[i]) {
int y = v[i];
if (dcc[y] || cut[i]) continue;
dfs2(y, cnt);
}
}//缩边双
void dfs1(int fa, int x) {
f[x] = fa; dep[x] = dep[fa] + 1; len[x] = len[fa] + (size[x] > 1); nmsl[x] = 1;
for (int i = 0; i < a[x].size(); i++) {
int y = a[x][i];
if (y == fa) continue;
dfs1(x, y);
nmsl[x] += nmsl[y];
if (son[x] == 0 || nmsl[son[x]] < nmsl[y]) son[x] = y;
}
}
void dfs3(int x, int t) {
top[x] = t;
if (son[x] == 0) return;
dfs3(son[x], t);
for (int i = 0; i < a[x].size(); i++) {
int y = a[x][i];
if (y == f[x] || y == son[x]) continue;
dfs3(y, y);
}
}//预处理树剖求LCA
int ask(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
x = f[top[x]];
}
return dep[x] < dep[y] ? x : y;
}
ll power(int a, int b) {
ll res = 1;
while (b) {
if (b & 1) res = 1ll * res * a % mod;
a = 1ll * a * a % mod; b >>= 1;
}
return res;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v; cin >> u >> v;
add(u, v); add(v, u);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) dfs(0, i);
for (int i = 1; i <= n; i++)
if (!dcc[i])
dfs2(i, ++lza);
for (int i = 1; i <= n; i++)
for (int j = head[i]; j; j = nxt[j]) {
int x = v[j];
if (dcc[i] != dcc[x]) a[dcc[i]].push_back(dcc[x]);
}
dfs1(0, 1); dfs3(1, 1);
cin >> q;
for (int i = 1; i <= q; i++) {
int x, y; cin >> x >> y; x = dcc[x], y = dcc[y];
int lca = ask(x, y);
cout << power(2, len[x] + len[y] - len[lca] * 2 + (size[lca] > 1)) << endl;//由于求的是点权和，因此特判lca这个点
}
return 0;
}
```