#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, mod = 1e9 + 7;
int n, m, q, top, col, cnt, st[N], len[N], size[N], dfn[N], bl[N], son[N], S[N],
    w[N], T[N], low[N], bin[N], dep[N], f[N];
char sc[N][10];
vector<int> e[N], v[N];
int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9')
    x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  return f * x;
}
void Tarjan(int x) {
  dfn[x] = low[x] = ++cnt;
  st[++top] = x;
  for (int i = 0; i < e[x].size(); i++) {
    int y = e[x][i];
    if (!dfn[y]) {
      Tarjan(y);
      low[x] = min(low[x], low[y]);
      if (low[y] == dfn[x]) {
        if (st[top] == y) {
          top--;
          v[x].push_back(y);
          v[y].push_back(x);
          continue;
        }
        size[++col] = 1;
        while (1) {
          int z = st[top--];
          size[col]++;
          bl[z] = col;
          v[z].push_back(col);
          v[col].push_back(z);
          if (z == y) break;
        }
        bl[x] = col;
        v[x].push_back(col);
        v[col].push_back(x);
      }
    } else
      low[x] = min(low[x], dfn[y]);
  }
}
void dfs(int x, int fa) {
  S[x] = 1;
  f[x] = fa;
  dep[x] = dep[fa] + 1;
  w[x] = w[fa];
  if (size[x] > 2)
    w[x]--;
  else if (size[bl[x]] > 2)
    w[x]++;
  for (int i = 0; i < v[x].size(); i++) {
    int y = v[x][i];
    if (y == fa) continue;
    dfs(y, x);
    S[x] += S[y];
    if (S[y] > S[son[x]]) son[x] = y;
  }
}
void dfs2(int x, int fa) {
  T[x] = fa;
  if (!son[x]) return;
  dfs2(son[x], fa);
  for (int i = 0; i < v[x].size(); i++) {
    int y = v[x][i];
    if (T[y]) continue;
    dfs2(y, y);
  }
}
int lca(int x, int y) {
  while (T[x] ^ T[y]) {
    if (dep[T[x]] > dep[T[y]])
      x = f[T[x]];
    else
      y = f[T[y]];
  }
  return dep[x] > dep[y] ? y : x;
}
int main() {
  n = read(), m = read();
  col = n;
  for (int i = 1, x, y; i <= m; i++) {
    x = read(), y = read();
    e[x].push_back(y);
    e[y].push_back(x);
  }
  Tarjan(1);
  bin[0] = 1;
  sc[0][len[0]++] = '1';
  for (int i = 1; i <= col; i++) {
    bin[i] = bin[i - 1] * 2 % mod;
    int x = bin[i];
    while (x) {
      sc[i][len[i]++] = '0' + x % 10;
      x /= 10;
    }
  }
  dfs(1, 0);
  dfs2(1, 1);
  q = read();
  for (int i = 1, x, y, z; i <= q; i++) {
    x = read(), y = read();
    z = lca(x, y);
    z = w[x] + w[y] - w[z] - w[f[z]];
    for (int j = len[z] - 1; j > -1; j--) putchar(sc[z][j]);
    putchar('\n');
  }
  return 0;
}
