#include <bits/stdc++.h>
using namespace std;
struct UF {
  int data[102000];
  void init() { memset((data), (-1), sizeof(data)); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  bool find(int x, int y) { return root(x) == root(y); }
  void uni(int x, int y) {
    x = root(x);
    y = root(y);
    if (x != y) {
      if (data[x] < data[y]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
  }
};
long long power(long long a, long long b) {
  const long long mod = 1000000007;
  if (b == 0) return 1LL;
  if (b % 2)
    return (a * power(a, b - 1)) % mod;
  else {
    long long x = power(a, b / 2);
    return (x * x) % mod;
  }
}
struct RMQ {
  static const int n = 1 << 19;
  long long data[2 * n];
  int ref[2 * n];
  void init() {
    for (int i = 0; i < (int)(2 * n); ++i) {
      data[i] = 1LL << 50;
      ref[i] = i >= n ? i - n : 0;
    }
  }
  void overwrite(int pos, long long value) {
    data[n + pos] = value;
    pos = (n + pos) / 2;
    while (pos > 1) {
      int lpos = pos * 2, rpos = pos * 2 + 1;
      data[pos] = min(data[lpos], data[rpos]);
      ref[pos] = (data[lpos] < data[rpos]) ? ref[lpos] : ref[rpos];
      pos = pos / 2;
    }
  }
  int sub(int fr, int to, int node, int la, int ra) {
    if (ra <= fr || to <= la) return -1;
    if (fr <= la && ra <= to) return ref[node];
    int vl = sub(fr, to, node * 2 + 0, la, (la + ra) / 2);
    int vr = sub(fr, to, node * 2 + 1, (la + ra) / 2, ra);
    if (vl == -1) return vr;
    if (vr == -1) return vl;
    return (data[n + vl] < data[n + vr]) ? vl : vr;
  }
  int get_min(int fr, int to) { return sub(fr, to, 1, 0, n); }
};
struct E {
  int fr, to;
  E(int fr, int to) : fr(fr), to(to) {}
};
void add_edge(vector<vector<E> >& vg, int fr, int to) {
  vg[fr].push_back(E(fr, to));
  vg[to].push_back(E(to, fr));
}
vector<vector<E> > vg, vh;
int cuc[102000];
UF uf;
bool vis[102000];
vector<int> lg;
void dfs(int now, int prev) {
  if (vis[now]) {
    if (uf.find(now, lg.back())) return;
    for (int i = (int)((lg).size()) - 1; i >= 0; --i) {
      if (lg[i] == now) break;
      uf.uni(lg[i], now);
    }
    cuc[uf.root(now)] = 1;
    return;
  }
  vis[now] = true;
  lg.push_back(now);
  for (__typeof((vg[now]).begin()) it = (vg[now]).begin();
       it != (vg[now]).end(); ++it)
    if (it->to != prev) dfs(it->to, now);
  lg.pop_back();
}
int csum[122222], vis2[122222];
int depth[222222], ids[222222], vs[222222];
void dfs2(int now, int su, int de, int& idx) {
  if (vis2[now]) return;
  vis2[now] = true;
  ids[now] = idx;
  csum[now] = su + cuc[now];
  vs[idx] = now;
  depth[idx++] = de;
  for (__typeof((vh[now]).begin()) it = (vh[now]).begin();
       it != (vh[now]).end(); ++it)
    if (!vis2[it->to]) {
      dfs2(it->to, su + cuc[now], de + 1, idx);
      vs[idx] = now;
      depth[idx++] = de;
    }
}
RMQ st;
int main() {
  int N, M;
  while (scanf("%d%d", &N, &M) != EOF) {
    vg = vector<vector<E> >(N);
    for (int i = 0; i < (int)(M); ++i) {
      int a, b;
      scanf("%d%d", &a, &b);
      a--;
      b--;
      add_edge(vg, a, b);
    }
    memset((cuc), (0), sizeof(cuc));
    memset((vis), (0), sizeof(vis));
    uf.init();
    lg.clear();
    dfs(0, -1);
    vh = vector<vector<E> >(N);
    for (int i = 0; i < (int)(N); ++i)
      for (__typeof((vg[i]).begin()) it = (vg[i]).begin(); it != (vg[i]).end();
           ++it) {
        int a = uf.root(it->fr), b = uf.root(it->to);
        if (a == b) continue;
        add_edge(vh, a, b);
      }
    int root = uf.root(0);
    int kkkk = 0;
    memset((depth), (0), sizeof(depth));
    memset((vis2), (0), sizeof(vis2));
    memset((vs), (-1), sizeof(vs));
    dfs2(root, 0, 0, kkkk);
    st.init();
    for (int i = 0; i < (int)(2 * N); ++i) st.overwrite(i, depth[i]);
    int K;
    scanf("%d", &K);
    for (int iter = 0; iter < (int)(K); ++iter) {
      int a, b;
      scanf("%d%d", &a, &b);
      a--;
      b--;
      a = uf.root(a);
      b = uf.root(b);
      if (a == b) {
        cout << (1 << cuc[a]) << endl;
        continue;
      }
      if (ids[a] > ids[b]) swap(a, b);
      int lca = vs[st.get_min(ids[a], ids[b] + 1)];
      int ccc = csum[a] + csum[b] - 2 * csum[lca] + cuc[lca];
      cout << power(2, ccc) << endl;
    }
  }
}
