#include <bits/stdc++.h>
using namespace std;
template <typename T>
T read1() {
  T t = 0;
  char k;
  bool v = 0;
  do (k = getchar()) == '-' && (v = 1);
  while ('0' > k || k > '9');
  while ('0' <= k && k <= '9')
    t = (t << 3) + (t << 1) + (k ^ '0'), k = getchar();
  return v ? -t : t;
}
int s, m, dfn[100005], low[100005], t, f[100005], bel[100005], cnt, d[100005],
    h[100005], up[100005][20];
stack<int> sta;
vector<int> G[100005], X[100005];
long long ans = 1, tans;
int Find(int x) { return x ^ f[x] ? f[x] = Find(f[x]) : x; }
void Merge(int x, int y) { f[Find(x)] = Find(y); }
void tarjan(int n, int fa) {
  dfn[n] = low[n] = ++t;
  d[n] = fa;
  sta.push(n);
  for (int i = 0; i < G[n].size(); ++i)
    if (!dfn[G[n][i]])
      tarjan(G[n][i], n), low[n] = min(low[n], low[G[n][i]]);
    else if (G[n][i] ^ fa)
      low[n] = min(low[n], dfn[G[n][i]]);
  if (dfn[n] == low[n]) {
    ++cnt;
    do {
      n = sta.top();
      ++f[cnt];
      bel[n] = cnt;
      sta.pop();
    } while (dfn[n] != low[n]);
    f[cnt] = f[cnt] > 1;
  }
}
void dfs(int n, int fa) {
  h[n] = h[fa] + 1;
  f[n] += f[fa];
  up[n][0] = fa;
  for (int i = 0; up[n][i + 1] = up[up[n][i]][i]; ++i)
    ;
  for (int i = 0; i < X[n].size(); ++i) dfs(X[n][i], n);
}
int qkpow(int n) {
  if (n < 63) return (1ll << n) % 1000000007;
  long long t = qkpow(n >> 1);
  t = t * t % 1000000007;
  if (n & 1) t = t * 2 % 1000000007;
  return t;
}
int lca(int x, int y) {
  if (h[x] < h[y]) swap(x, y);
  for (int i = 0, w = h[x] - h[y]; w; ++i)
    if (w >> i & 1) {
      w ^= 1 << i;
      x = up[x][i];
    }
  if (x == y) return x;
  for (int i = 20; i--;)
    if (up[x][i] ^ up[y][i]) {
      x = up[x][i];
      y = up[y][i];
    }
  return up[x][0];
}
int main() {
  s = read1<long long>();
  m = read1<long long>();
  for (int i = 1; i <= m; ++i) {
    int u = read1<long long>(), v = read1<long long>();
    G[u].push_back(v);
    G[v].push_back(u);
  }
  tarjan(1, 0);
  for (int i = 2; i <= s; ++i)
    if (low[i] > dfn[d[i]]) X[bel[d[i]]].push_back(bel[i]);
  dfs(bel[1], 0);
  for (int T = read1<long long>(); T--;) {
    int l = bel[read1<long long>()], r = bel[read1<long long>()], k = lca(l, r);
    printf("%d\n", qkpow(f[l] + f[r] - f[k] - f[up[k][0]]));
  }
  return 0;
}
