#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:50000000")
using namespace std;
int tt[1000000], kix[1000000], num[1000000], degree[1000000], black[1000000],
    fix[1000000];
vector<int> q, g[1000000];
int pirveli, p, i, j, n, m, k, a, b;
int par[100005][20];
long long ans[1000000];
void go(int x, int prev = -1) {
  fix[x] = 1;
  q.push_back(x);
  for (int i = 0; i < g[x].size(); i++) {
    int nxt = g[x][i];
    if (nxt == prev) continue;
    if (fix[nxt] == 0) {
      go(nxt, x);
      continue;
    }
    if (num[nxt] != -1) continue;
    for (int j = q.size() - 1; j >= 0; j--) {
      num[q[j]] = nxt;
      if (q[j] == nxt) break;
    }
  }
  q.pop_back();
}
void DFS(int v, int prev, int deg, int raod) {
  kix[v] = 1;
  degree[v] = deg;
  if (tt[v] != 1) raod++;
  black[v] = raod;
  par[v][0] = num[prev];
  for (int j = 1; j <= 19; j++)
    if (par[v][j - 1] == -1)
      par[v][j] = -1;
    else
      par[v][j] = par[par[v][j - 1]][j - 1];
  for (int i = 0; i < g[v].size(); i++) {
    int nxt = g[v][i];
    if (nxt == prev) continue;
    DFS(nxt, v, deg + 1, raod);
  }
}
int LCA(int a, int b) {
  for (int i = 18; i >= 0; i--) {
    if (degree[a] - (1 << i) >= degree[b]) {
      a = par[a][i];
    }
  }
  if (a == b) return a;
  for (int i = 18; i >= 0; i--) {
    if (par[a][i] != par[b][i]) {
      a = par[a][i];
      b = par[b][i];
    }
  }
  return par[a][0];
}
int main() {
  cin >> n >> m;
  for (i = 0; i < m; i++) {
    cin >> a >> b;
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  for (i = 0; i < n; i++) num[i] = -1;
  go(0);
  for (i = 0; i <= n; i++)
    for (j = 0; j <= 20; j++) par[i][j] = -1;
  for (i = 0; i < n; i++) {
    if (num[i] == -1 || num[i] == i) continue;
    for (j = 0; j < g[i].size(); j++) g[num[i]].push_back(g[i][j]);
  }
  for (i = 0; i < n; i++)
    if ((num[i] == -1 || num[i] == i)) {
      for (j = 0; j < g[i].size(); j++) {
        int nxt = g[i][j];
        if (num[nxt] == i) {
          g[i][j] = g[i].back();
          g[i].pop_back();
          j--;
        } else if (num[nxt] == -1)
          continue;
        else
          g[i][j] = num[nxt];
      }
    }
  if (num[0] == -1)
    pirveli = 0;
  else
    pirveli = num[0];
  for (i = 0; i < n; i++)
    if (num[i] == -1) {
      num[i] = i;
      tt[i] = 1;
    }
  DFS(pirveli, -1, 0, 0);
  ans[0] = 1;
  for (i = 1; i <= n; i++) ans[i] = ans[i - 1] * 2 % 1000000007;
  cin >> k;
  while (k--) {
    cin >> a >> b;
    a = num[a - 1];
    b = num[b - 1];
    if (degree[a] < degree[b]) swap(a, b);
    p = LCA(a, b);
    p = num[p];
    cout << ans[black[a] + black[b] - 2 * black[p] + (tt[p] == 0)] << endl;
  }
}
