#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const long long mod = 1e9 + 7;
struct Edge {
  int ver, nxt;
} e[2 * MAXN], e2[2 * MAXN];
int head[MAXN], head2[MAXN], tot = 0, tot2 = 0;
void add(int u, int v) {
  e[++tot].ver = v;
  e[tot].nxt = head[u];
  head[u] = tot;
}
void add2(int u, int v) {
  e2[++tot2].ver = v;
  e2[tot2].nxt = head2[u];
  head2[u] = tot2;
}
int dfn[MAXN], low[MAXN], tim = 0, vis[MAXN];
stack<int> s;
int scc[MAXN], sz[MAXN], cnt = 0;
void tarjan(int u, int fa) {
  int i;
  dfn[u] = low[u] = ++tim;
  vis[u] = 114514;
  s.push(u);
  for (i = head[u]; i; i = e[i].nxt) {
    int v = e[i].ver;
    if (v == fa || vis[v] == 1919810) continue;
    if (!vis[v]) tarjan(v, u);
    low[u] = min(low[u], low[v]);
  }
  if (dfn[u] == low[u]) {
    cnt++;
    while (1) {
      int tp = s.top();
      s.pop();
      vis[tp] = 1919810;
      scc[tp] = cnt;
      sz[cnt]++;
      if (u == tp) break;
    }
  }
  return;
}
int dep[MAXN], t[MAXN], F[MAXN][18];
void dfs(int u, int fa) {
  dep[u] = dep[fa] + 1;
  if (u == 1)
    t[u] = sz[u] > 1;
  else
    t[u] = t[fa] + (sz[u] > 1);
  F[u][0] = fa;
  int i;
  for (i = head2[u]; i; i = e2[i].nxt) {
    int v = e2[i].ver;
    if (v == fa) continue;
    dfs(v, u);
  }
  return;
}
int LCA(int u, int v) {
  int i;
  if (dep[u] > dep[v]) swap(u, v);
  for (i = 0; i <= 17; i++)
    if (((dep[v] - dep[u]) >> i) & 1) v = F[v][i];
  if (u == v) return u;
  for (i = 17; i >= 0; i--) {
    if (F[u][i] != F[v][i]) {
      u = F[u][i];
      v = F[v][i];
    }
  }
  return F[u][0];
}
long long qpow(long long base, long long p) {
  long long res = 1;
  while (p) {
    if (p & 1) res = (res * base) % mod;
    base = (base * base) % mod;
    p >>= 1;
  }
  return res;
}
int main() {
  int n, m, q, i, j;
  scanf("%d %d", &n, &m);
  for (i = 1; i <= m; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    add(u, v);
    add(v, u);
  }
  memset(dfn, 0, sizeof(dfn));
  memset(vis, 0, sizeof(vis));
  for (i = 1; i <= n; i++)
    if (!vis[i]) tarjan(i, 0);
  for (i = 1; i <= n; i++) {
    for (j = head[i]; j; j = e[j].nxt) {
      int v = e[j].ver;
      if (scc[i] == scc[v]) continue;
      add2(scc[i], scc[v]);
    }
  }
  dep[0] = -1;
  t[0] = 0;
  dfs(1, 0);
  for (i = 1; i <= 17; i++)
    for (j = 1; j <= cnt; j++) F[j][i] = F[F[j][i - 1]][i - 1];
  scanf("%d", &q);
  for (i = 1; i <= q; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    int lca = LCA(scc[u], scc[v]);
    int ring = t[scc[u]] + t[scc[v]] - t[lca] * 2 + (sz[lca] > 1);
    printf("%lld\n", qpow(2ll, 1ll * ring));
  }
  return 0;
}
