#include <bits/stdc++.h>
using namespace std;
int times, top, bcnt;
int dfn[100100], low[100010], stk[100010], instk[100010], belong[100010];
vector<int> adj[100010];
vector<int> edge[100010];
int cal[100010];
void tarjan(int u, int pre1) {
  int sz, v;
  dfn[u] = low[u] = ++times;
  stk[++top] = u;
  instk[u] = 1;
  for (sz = 0; sz < adj[u].size(); sz++) {
    v = adj[u][sz];
    if (v == pre1) continue;
    if (dfn[v] == 0) {
      tarjan(v, u);
      low[u] = min(low[u], low[v]);
    } else if (instk[v])
      low[u] = min(low[u], dfn[v]);
  }
  if (dfn[u] == low[u]) {
    bcnt++;
    int tt = 0;
    int j;
    do {
      j = stk[top--];
      if (tt++ > 1) cal[bcnt] = 1;
      belong[j] = bcnt;
      instk[j] = 0;
    } while (j != u);
  }
}
int n, m;
void build() {
  for (int i = 1; i <= n; i++) edge[i].clear();
  for (int i = 1; i <= n; i++)
    for (int j = 0; j < adj[i].size(); j++) {
      int u = belong[i];
      int v = belong[adj[i][j]];
      if (u == v) continue;
      edge[u].push_back(v);
    }
  return;
}
void init() {
  for (int i = 1; i <= n; i++) adj[i].clear();
  top = times = bcnt = 0;
  memset(stk, 0, sizeof(stk));
  memset(low, 0, sizeof(low));
  memset(dfn, 0, sizeof(dfn));
  memset(instk, 0, sizeof(instk));
  memset(cal, 0, sizeof(cal));
}
int num[200010], dep[200010], pre[200010], dp[100010];
int minn[200010][20], ans[200010][20];
int tot;
void dfs(int x, int deep, int v) {
  num[++tot] = x;
  dep[tot] = deep;
  pre[x] = tot;
  for (int i = 0; i < edge[x].size(); i++) {
    int to = edge[x][i];
    if (to == v) continue;
    dfs(to, deep + 1, x);
    num[++tot] = x;
    dep[tot] = deep;
  }
  return;
}
void makermq() {
  for (int i = 1; i <= tot; i++) minn[i][0] = dep[i], ans[i][0] = num[i];
  for (int j = 1; (1 << j) <= tot; j++)
    for (int i = 1; i + (1 << j) - 1 <= tot; i++) {
      if (minn[i][j - 1] < minn[i + (1 << (j - 1))][j - 1])
        minn[i][j] = minn[i][j - 1], ans[i][j] = ans[i][j - 1];
      else
        minn[i][j] = minn[i + (1 << (j - 1))][j - 1],
        ans[i][j] = ans[i + (1 << (j - 1))][j - 1];
    }
  return;
}
int query(int l, int r) {
  if (l > r) {
    l ^= r;
    r ^= l;
    l ^= r;
  }
  int dx = r - l + 1, k = 0;
  while ((1 << (k + 1)) < dx) k++;
  if (minn[l][k] < minn[r - (1 << k) + 1][k])
    return ans[l][k];
  else
    return ans[r - (1 << k) + 1][k];
}
int vis[100010];
void cal1() {
  memset(vis, 0, sizeof(vis));
  dp[1] = cal[1];
  queue<int> que;
  que.push(1);
  vis[1] = 1;
  while (!que.empty()) {
    int x = que.front();
    que.pop();
    for (int i = 0; i < edge[x].size(); i++) {
      int to = edge[x][i];
      if (vis[to]) continue;
      dp[to] = dp[x] + cal[to];
      que.push(to);
      vis[to] = 1;
    }
  }
  return;
}
int getdis(int x, int y) {
  x = belong[x];
  y = belong[y];
  if (x < 0 || y < 0) {
    while (1) {
    }
  }
  int t1 = pre[x];
  int t2 = pre[y];
  int t = query(t1, t2);
  return dp[x] + dp[y] - 2 * dp[t] + cal[t];
}
int ans1[100010];
int main() {
  ans1[0] = 1;
  for (int i = 1; i <= 100000; i++) {
    ans1[i] = ans1[i - 1] * 2;
    if (ans1[i] >= 1000000007) ans1[i] -= 1000000007;
  }
  while (cin >> n >> m) {
    init();
    for (int i = 1; i <= m; i++) {
      int a, b;
      cin >> a >> b;
      adj[a].push_back(b);
      adj[b].push_back(a);
    }
    for (int i = 1; i <= n; i++)
      if (dfn[i] == 0) tarjan(i, -1);
    build();
    tot = 0;
    dfs(1, 0, -1);
    makermq();
    cal1();
    int k;
    cin >> k;
    for (int i = 1; i <= k; i++) {
      int a, b;
      cin >> a >> b;
      cout << ans1[getdis(a, b)] << endl;
    }
  }
  return 0;
}
