#include <vector>
using namespace std;

// 演算法 / Algorithm:
// 路徑有 k 條邊時,使成本為奇數的方法數 = 2^(k-1)(k=0 時為 0)。
// With k edges on the path, odd-cost assignments = 2^(k-1) (0 when k==0).
// 用 BFS 求深度/父節點,倍增 LCA 求兩點距離 k。
// BFS for depth/parent, binary-lifting LCA for the distance k.

class Solution {
public:
    static const int MOD = 1000000007;            // 模數 / the modulus
    static const int LOG = 17;                     // 跳躍層數,2^17 > 1e5 / lifting levels

    vector<int> assignEdgeWeights(vector<vector<int>>& edges,
                                  vector<vector<int>>& queries) {
        int n = edges.size() + 1;                  // 節點數 / number of nodes

        // 鄰接表:adj[u] 是 u 所有鄰居的清單 / adjacency list: adj[u] holds u's neighbors
        vector<vector<int>> adj(n + 1);
        for (auto& e : edges) {                    // range-for 走訪每條邊 / range-based for over edges
            adj[e[0]].push_back(e[1]);             // 無向邊兩個方向都加 / add both directions
            adj[e[1]].push_back(e[0]);
        }

        vector<int> depth(n + 1, 0);               // 每點深度 / depth of each node
        // up 是二維表,up[k][v] = v 往上 2^k 步的祖先 / up[k][v] = 2^k-th ancestor of v
        vector<vector<int>> up(LOG, vector<int>(n + 1, 0));

        // BFS 從根 1 / BFS from root 1
        vector<char> vis(n + 1, 0);                // 訪問標記 / visited flags
        vector<int> q;                             // 用 vector 當佇列 / vector used as a queue
        q.push_back(1); vis[1] = 1; up[0][1] = 0;  // 根的父節點是哨兵 0 / root's parent = sentinel 0
        for (size_t i = 0; i < q.size(); i++) {    // i 隨 q 變長持續推進 / i advances as q grows
            int u = q[i];                          // 取出目前節點 / current node
            for (int w : adj[u]) {                 // 走訪鄰居 / iterate neighbors
                if (!vis[w]) {                     // 沒訪問過才展開 / expand only if unvisited
                    vis[w] = 1;
                    depth[w] = depth[u] + 1;       // 子節點深度 / child depth
                    up[0][w] = u;                  // 直接父節點 / immediate parent
                    q.push_back(w);                // 入列 / enqueue
                }
            }
        }

        // 倍增填表 / build the lifting table
        for (int k = 1; k < LOG; k++)
            for (int v = 1; v <= n; v++)
                // 2^k 步 = 兩次 2^(k-1) 步 / a 2^k jump = two 2^(k-1) jumps
                up[k][v] = up[k - 1][up[k - 1][v]];

        // 預先算 2 的次方 / precompute powers of two
        vector<long long> pw(n + 1);
        pw[0] = 1;
        for (int i = 1; i <= n; i++) pw[i] = pw[i - 1] * 2 % MOD;

        // 求 LCA 的 lambda / a lambda computing the LCA of two nodes
        auto lca = [&](int a, int b) {
            if (depth[a] < depth[b]) swap(a, b);   // 讓 a 較深 / make a the deeper one
            int diff = depth[a] - depth[b];        // 深度差 / depth gap
            for (int k = 0; k < LOG; k++)          // 把 a 拉到和 b 同深度 / lift a to b's depth
                if (diff & (1 << k)) a = up[k][a]; // 第 k 位元為 1 就跳 2^k / jump 2^k if bit set
            if (a == b) return a;                  // b 已是祖先 / b is already the ancestor
            for (int k = LOG - 1; k >= 0; k--)     // 兩點一起往上 / lift both together
                if (up[k][a] != up[k][b]) { a = up[k][a]; b = up[k][b]; }
            return up[0][a];                       // 再一步即 LCA / one step up is the LCA
        };

        vector<int> ans;
        ans.reserve(queries.size());               // 預留空間避免重複擴容 / reserve to avoid reallocs
        for (auto& qy : queries) {
            int u = qy[0], v = qy[1];              // 結構化取兩端 / the two query endpoints
            int l = lca(u, v);                     // 最近公共祖先 / their LCA
            int dist = depth[u] + depth[v] - 2 * depth[l]; // 路徑邊數 / edges on the path
            ans.push_back(dist == 0 ? 0 : (int)pw[dist - 1]); // 0 或 2^(k-1) / 0 or 2^(k-1)
        }
        return ans;
    }
};