#include <bits/stdc++.h>
using namespace std;
int get() {
  int x = 0;
  char s = getchar();
  while (s < '0' || s > '9') s = getchar();
  while (s >= '0' && s <= '9')
    x = (x << 3) + (x << 1) + (s ^ 48), s = getchar();
  return x;
}
int Min(const int x, const int y) {
  if (x < y) return x;
  return y;
}
const int M = 1e5 + 5, mo = 1e9 + 7;
int n, m, head[M], cntedge, vis[M], dfn[M], low[M], tot, cntscc, scc[M], siz[M],
    dep[M], f[M][17], w[M];
vector<int> G[M];
stack<int> st;
struct edge {
  int to, nxt;
  edge() {}
  edge(const int T, const int NX) { to = T, nxt = NX; }
} e[M << 1];
void add(const int u, const int v) {
  e[++cntedge] = edge(v, head[u]), head[u] = cntedge;
}
int pow(int x, int k) {
  int ans = 1;
  while (k) {
    if (k & 1) ans = 1ll * ans * x % mo;
    x = 1ll * x * x % mo;
    k >>= 1;
  }
  return ans;
}
void tarjan(const int u, const int fa) {
  dfn[u] = low[u] = ++tot;
  vis[u] = 1;
  st.push(u);
  int v;
  for (int i = head[u]; i; i = e[i].nxt) {
    v = e[i].to;
    if (v == fa || vis[v] == 2) continue;
    if (!vis[v]) tarjan(v, u);
    low[u] = Min(low[u], low[v]);
  }
  if (dfn[u] == low[u]) {
    ++cntscc;
    do {
      v = st.top(), st.pop();
      scc[v] = cntscc;
      vis[v] = 2;
      ++siz[cntscc];
    } while (v ^ u);
  }
}
void dfs(const int x, const int fa) {
  dep[x] = dep[fa] + 1;
  f[x][0] = fa;
  w[x] = w[fa] + (siz[x] > 1);
  for (int i = 1; i < 17; ++i) f[x][i] = f[f[x][i - 1]][i - 1];
  for (int i = 0; i < G[x].size(); ++i)
    if (G[x][i] ^ fa) dfs(G[x][i], x);
}
void adjust(int &u, const int val) {
  for (int i = 16; i >= 0; --i)
    if (dep[f[u][i]] >= val) u = f[u][i];
}
int lca(int u, int v) {
  if (dep[u] > dep[v])
    adjust(u, dep[v]);
  else if (dep[u] < dep[v])
    adjust(v, dep[u]);
  if (u == v) return u;
  for (int i = 16; i >= 0; --i)
    if (f[u][i] ^ f[v][i]) u = f[u][i], v = f[v][i];
  return f[u][0];
}
int main() {
  n = get(), m = get();
  for (int u, v; m--;) {
    u = get(), v = get();
    add(u, v), add(v, u);
  }
  for (int i = 1; i <= n; ++i)
    if (!dfn[i]) tarjan(i, 0);
  for (int i = 1; i <= n; ++i)
    for (int j = head[i]; j; j = e[j].nxt)
      if (scc[i] ^ scc[e[j].to]) G[scc[i]].push_back(scc[e[j].to]);
  dfs(1, 0);
  for (int q = get(), u, v, x, k; q--;) {
    u = scc[get()], v = scc[get()], x = lca(u, v);
    k = w[u] + w[v] - (w[x] << 1) + (siz[x] > 1);
    printf("%d\n", pow(2, k));
  }
  return 0;
}
