#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000002;
const long long INFLL = 100000000000000000ll;
const long long MOD = 1000000007;
int Cycle[100005], N, Real[100005], Pos[100005], V[100005], P[100005][20],
    D[100005], Edg, K;
long long M[100005];
vector<int> E[100005], E2[100005];
void dfs(int n, int p, int from) {
  if (Real[n] != n) return;
  if (Pos[n] > 0) {
    Cycle[n] = 1;
    for (int i = (Pos[n] + 1); i <= (p - 1); i++) Real[V[i]] = n;
    return;
  }
  Pos[n] = p;
  V[p] = n;
  for (int v : E[n])
    if (v != from) dfs(v, p + 1, n);
}
void dfs2(int n, int p, int d, long long mult) {
  D[n] = d;
  M[n] = mult;
  P[n][0] = p;
  for (int v : E2[n])
    if (v != p) dfs2(v, n, d + 1, mult + Cycle[v]);
}
int lca(int a, int b) {
  if (D[a] > D[b]) return lca(b, a);
  int diff = D[b] - D[a];
  for (int i = (0); i <= (17); i++)
    if (diff & (1 << i)) b = P[b][i];
  if (a == b) return a;
  for (int i = (17); i >= (0); i--)
    if (P[a][i] != P[b][i]) a = P[a][i], b = P[b][i];
  return P[a][0];
}
long long exp(long long n, int e) {
  if (e == 0) return 1;
  if (e % 2) return (exp(n, e - 1) * n) % MOD;
  long long q = exp(n, e / 2);
  return (q * q) % MOD;
}
int main() {
  cin >> N >> Edg;
  for (int i = (1); i <= (Edg); i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    E[a].push_back(b), E[b].push_back(a);
  }
  for (int i = (1); i <= (N); i++) Real[i] = i;
  dfs(1, 1, 0);
  for (int i = (1); i <= (N); i++)
    for (int v : E[i]) {
      int v1 = Real[i];
      int v2 = Real[v];
      if (v1 != v2) E2[v1].push_back(v2);
    }
  dfs2(Real[1], 0, 1, Cycle[Real[1]]);
  for (int j = (1); j <= (17); j++)
    for (int i = (1); i <= (N); i++) P[i][j] = P[P[i][j - 1]][j - 1];
  cin >> K;
  for (int kk = (1); kk <= (K); kk++) {
    int a, b;
    scanf("%d %d", &a, &b);
    a = Real[a], b = Real[b];
    if (a == b) {
      printf("2\n");
      continue;
    }
    int l = lca(a, b);
    int par = P[l][0];
    long long val = M[a] + M[b] - M[par] - M[par] - Cycle[l];
    printf("%I64d\n", exp(2, val));
  }
}
