#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100005;
int vertexc, edgec;
int v;
vector<int> adj[MAX_N];
int lvl[MAX_N];
int dp[MAX_N];
int cycle_id[MAX_N];
int cycle_id_node[MAX_N];
vector<int> adj2[MAX_N];
int cid;
int p[100005][25 + 1], par[100005], l[100005];
int cnt[100005][25 + 1];
void assigncycle(int vertex, int parent) {
  dp[vertex] = 0;
  for (int nxt : adj[vertex]) {
    if (lvl[nxt] == 0) {
      lvl[nxt] = lvl[vertex] + 1;
      assigncycle(nxt, vertex);
      dp[vertex] += dp[nxt];
      if (dp[nxt] > 0) {
        cycle_id[vertex] = cycle_id[nxt];
      }
    } else if (lvl[nxt] < lvl[vertex]) {
      if (nxt != parent) {
        cycle_id[vertex] = ++cid;
        cycle_id_node[cid] = vertex;
      }
      dp[vertex]++;
    } else if (lvl[nxt] > lvl[vertex]) {
      dp[vertex]--;
    }
  }
  dp[vertex]--;
}
void newtree(int vertex, int parent) {
  for (int i = 1; i < vertexc + 1; i++) {
    if (cycle_id[i] == 0) {
      for (auto x : adj[i]) {
        if (cycle_id[x])
          adj2[i].push_back(cycle_id_node[cycle_id[x]]);
        else
          adj2[i].push_back(x);
      }
    } else {
      for (auto x : adj[i]) {
        if (cycle_id[x] != cycle_id[i]) {
          if (cycle_id[x])
            adj2[cycle_id_node[cycle_id[i]]].push_back(
                cycle_id_node[cycle_id[x]]);
          else
            adj2[cycle_id_node[cycle_id[i]]].push_back(x);
        }
      }
    }
  }
}
void parent(int n, int b, int le) {
  par[n] = b;
  l[n] = le;
  for (auto x : adj2[n])
    if (!par[x]) parent(x, n, le + 1);
}
void preprocess() {
  if (cycle_id[1] != 0)
    parent(cycle_id_node[cycle_id[1]], -1, 0);
  else
    parent(1, -1, 0);
  for (int i = 1; i < v + 1; i++)
    for (int j = 1; j < 25 + 1; j++) p[i][j] = -1;
  for (int i = 1; i < v + 1; i++) {
    if (cycle_id[i] != 0 && cycle_id_node[cycle_id[i]] != i) continue;
    p[i][0] = par[i];
    cnt[i][0] = (cycle_id[par[i]] > 0 ? 1 : 0);
  }
  for (int j = 1; (1 << j) < v; j++) {
    for (int i = 1; i <= v; i++) {
      if (p[i][j - 1] != -1) {
        p[i][j] = p[p[i][j - 1]][j - 1];
        cnt[i][j] = cnt[i][j - 1] + cnt[p[i][j - 1]][j - 1];
      }
    }
  }
}
int lca(int u, int v) {
  if (l[u] < l[v]) swap(u, v);
  int d = l[u] - l[v];
  for (int i = 25; i >= 0; i--) {
    if (d >> i & 1) {
      u = p[u][i];
    }
  }
  if (u == v) return u;
  for (int j = 25; j >= 0; --j) {
    if ((p[u][j] != -1) and (p[u][j] != p[v][j])) {
      u = p[u][j];
      v = p[v][j];
    }
  }
  return par[u];
}
long long me(long long x, long long n) {
  long long r = 1;
  while (n > 0) {
    if (n % 2 == 1) r = (r * x) % 1000000007;
    x = (x * x) % 1000000007;
    n = n / 2;
  }
  return r;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> vertexc >> edgec;
  v = vertexc;
  for (int i = 0; i < edgec; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  lvl[1] = 1;
  assigncycle(1, 0);
  newtree(1, 0);
  preprocess();
  int queries;
  cin >> queries;
  for (int i = 0; i < queries; i++) {
    int a, b;
    cin >> a >> b;
    if (cycle_id[a] != 0) a = cycle_id_node[cycle_id[a]];
    if (cycle_id[b] != 0) b = cycle_id_node[cycle_id[b]];
    int top = lca(a, b);
    int u = a;
    int v = b;
    int cntu = cycle_id[a] > 0 ? 1 : 0;
    int cntv = cycle_id[b] > 0 ? 1 : 0;
    int du = l[u] - l[top];
    int dv = l[v] - l[top];
    for (int i = 25; i >= 0; i--) {
      if (du >> i & 1) {
        cntu += cnt[u][i];
        u = p[u][i];
      }
    }
    for (int i = 25; i >= 0; i--) {
      if (dv >> i & 1) {
        cntv += cnt[v][i];
        v = p[v][i];
      }
    }
    int tot = cntu + cntv;
    if (cycle_id[top] != 0) tot -= 1;
    cout << me(2, tot) << '\n';
  }
}
