#include <bits/stdc++.h>
using namespace std;
template <class T>
inline T gcd(T a, T b) {
  if (a < 0) return gcd(-a, b);
  if (b < 0) return gcd(a, -b);
  return (b == 0) ? a : gcd(b, a % b);
}
template <class T>
inline T lcm(T a, T b) {
  if (a < 0) return lcm(-a, b);
  if (b < 0) return lcm(a, -b);
  return a * (b / gcd(a, b));
}
template <class T>
T power(T N, T P) {
  return (P == 0) ? 1 : N * power(N, P - 1);
}
long long toInt64(string s) {
  long long r = 0;
  istringstream sin(s);
  sin >> r;
  return r;
}
double LOG(long long N, long long B) { return (log10l(N)) / (log10l(B)); }
string itoa(long long a) {
  if (a == 0) return "0";
  string ret;
  for (long long i = a; i > 0; i = i / 10) ret.push_back((i % 10) + 48);
  reverse(ret.begin(), ret.end());
  return ret;
}
vector<string> token(string a, string b) {
  const char *q = a.c_str();
  while (count(b.begin(), b.end(), *q)) q++;
  vector<string> oot;
  while (*q) {
    const char *e = q;
    while (*e && !count(b.begin(), b.end(), *e)) e++;
    oot.push_back(string(q, e));
    q = e;
    while (count(b.begin(), b.end(), *q)) q++;
  }
  return oot;
}
int Set(int N, int pos) { return N = N | (1 << pos); }
int reset(int N, int pos) { return N = N & ~(1 << pos); }
int check(int N, int pos) { return (N & (1 << pos)); }
int toggle(int N, int pos) {
  if (check(N, pos)) return N = reset(N, pos);
  return N = Set(N, pos);
}
void pbit(int N) {
  printf("(");
  for (int i = 10; i >= 0; i--) {
    bool x = check(N, i);
    cout << x;
  }
  puts(")");
}
int fx[] = {0, 0, 1, -1, 1, -1, 1, -1};
int fy[] = {-1, 1, 0, 0, -1, -1, 1, 1};
int P[200002][25], cost[200002];
int L[200002], T[200002];
int num[200002];
int compsz[200002];
int lca_query(int p, int q) {
  int tmp, log, i;
  if (L[p] < L[q]) tmp = p, p = q, q = tmp;
  for (log = 1; 1 << log <= L[p]; log++)
    ;
  log--;
  for (i = log; i >= 0; i--)
    if (L[p] - (1 << i) >= L[q]) p = P[p][i];
  if (p == q) return p;
  for (i = log; i >= 0; i--)
    if (P[p][i] != -1 && P[p][i] != P[q][i]) p = P[p][i], q = P[q][i];
  return T[p];
}
void lca_init(int N) {
  int i, j;
  memset(P, -1, sizeof(P));
  ;
  for (i = 1; i <= N; i++) P[i][0] = T[i];
  for (j = 1; 1 << j < N; j++)
    for (i = 1; i <= N; i++)
      if (P[i][j - 1] != -1) P[i][j] = P[P[i][j - 1]][j - 1];
}
vector<int> g[200002], tree[200002];
void tree_dfs(int par, int u, int dep, int cst) {
  cost[u] = cst;
  L[u] = dep;
  T[u] = par;
  for (int i = 0; i < (int)tree[u].size(); i++) {
    int v = tree[u][i];
    if (v == par) continue;
    tree_dfs(u, v, dep + 1, cst + (compsz[v] > 1));
  }
}
int vis[200002];
int ances[200002];
int ass = 0;
void dfs(int par, int u) {
  ances[u] = par;
  vis[u] = 1;
  for (int i = 0; i < (int)g[u].size(); i++) {
    int v = g[u][i];
    if (v == par) continue;
    if (!vis[v]) {
      dfs(u, v);
    } else if (vis[v] == 1) {
      ass++;
      int w = u;
      while (1) {
        num[w] = ass;
        compsz[ass]++;
        if (w == v) break;
        w = ances[w];
      }
    }
  }
  vis[u] = 2;
}
long long modf(long long n, long long p, long long m) {
  if (p == 0) return 1;
  if (p % 2 == 0) {
    long long ret = modf(n, p >> 1, m);
    return ((ret % m) * (ret % m)) % m;
  } else
    return ((n % m) * (modf(n, p - 1, m) % m)) % m;
}
int main() {
  int n, e;
  scanf("%d%d", &n, &e);
  for (int i = 1; i <= (int)e; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  ances[1] = -1;
  dfs(-1, 1);
  for (int i = 1; i <= (int)n; i++) {
    if (num[i] == 0) {
      ass++;
      num[i] = ass;
      compsz[ass]++;
    }
  }
  for (int u = 1; u <= (int)n; u++) {
    for (int j = 0; j < (int)g[u].size(); j++) {
      int v = g[u][j];
      if (num[u] == num[v]) continue;
      tree[num[u]].push_back(num[v]);
    }
  }
  tree_dfs(-1, num[1], 0, compsz[num[1]] > 1);
  lca_init(ass);
  int q;
  scanf("%d", &q);
  while (q--) {
    int a, b;
    scanf("%d%d", &a, &b);
    a = num[a];
    b = num[b];
    if (a == b)
      puts("2");
    else {
      int lca = lca_query(a, b);
      long long ret = cost[a] + cost[b] - 2 * cost[lca] + (compsz[lca] > 1);
      long long ans = modf(2, ret, 1000000007);
      cout << ans << endl;
    }
  }
}
