#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
bool vis[N];
vector<int> v[N], g[N];
int lop[N], bin[N], low[N];
int n, m, cnt, fa[N], tree[N], d[N], dep[N];
int f[N][25];
long long f2[N][25], q;
stack<int> st;
inline int ask(int x) { return (x == bin[x] ? x : bin[x] = ask(bin[x])); }
void join(int x, int y) {
  x = ask(x);
  y = ask(y);
  if (x != y) bin[x] = y;
}
void tarjin(int now) {
  st.push(now);
  low[now] = dep[now];
  for (int i = 0; i < v[now].size(); i++) {
    int to = v[now][i];
    if (!dep[to]) {
      fa[to] = now;
      dep[to] = dep[now] + 1;
      tarjin(to);
      low[now] = min(low[now], low[to]);
    } else if (to != fa[now])
      low[now] = min(low[now], dep[to]);
  }
  if (low[now] == dep[now]) {
    if (now)
      f[now][0] = fa[now] + 1;
    else
      f[now][0] = -1, d[now] = 1;
    while (st.top() != now) {
      lop[cnt]++;
      tree[st.top()] = cnt;
      join(st.top(), now);
      st.pop();
    }
    lop[cnt]++;
    tree[st.top()] = cnt;
    st.pop();
    if (lop[cnt] > 1)
      f2[now][0] = 2;
    else
      f2[now][0] = 1;
    cnt++;
  }
  return;
}
void dfs(int now) {
  vis[now] = true;
  if (ask(now) != ask(fa[now])) d[ask(now)] = d[ask(fa[now])] + 1;
  for (int i = 0; i < v[now].size(); i++) {
    int to = v[now][i];
    if (!vis[to]) dfs(to);
  }
}
void init() {
  dep[0] = 1;
  fa[0] = -1;
  tarjin(0);
  for (int i = 0; i < n; i++) f[i][0]--;
  f[0][0] = -1;
  for (int i = 0; i < n; i++)
    if (f[i][0] != -1) f[i][0] = ask(f[i][0]);
  dfs(0);
  for (int i = 1; i <= 20; i++) {
    for (int j = 0; j < n; j++) {
      if (f[j][i - 1] == -1)
        f[j][i] = -1;
      else
        f[j][i] = f[f[j][i - 1]][i - 1];
      f2[j][i] = f2[f[j][i - 1]][i - 1] * f2[j][i - 1] % mod;
    }
  }
}
long long lca(int x, int y) {
  long long res = 1;
  x = ask(x);
  y = ask(y);
  if (x == y) return f2[x][0];
  if (d[x] < d[y]) swap(x, y);
  for (int i = 18; i >= 0 && d[x] > d[y]; i--)
    if (f[x][i] != -1 && d[f[x][i]] >= d[y])
      res = res * f2[x][i] % mod, x = f[x][i];
  if (x == y) return res * f2[x][0] % mod;
  for (int i = 18; i >= 0 && x != y; i--)
    if (f[x][i] != -1 && f[y][i] != -1 && f[x][i] != f[y][i])
      res = res * f2[x][i] % mod * f2[y][i] % mod, x = f[x][i], y = f[y][i];
  return res * f2[x][0] % mod * f2[y][0] % mod * f2[f[x][0]][0] % mod;
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) bin[i] = i;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  init();
  cin >> q;
  while (q--) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    cout << lca(a, b) << "\n";
  }
  return 0;
}
