// 演算法 / Algorithm:
// 1) 用 BFS 從根節點 1 算出最大深度 d。
//    BFS from root (node 1) to find the maximum depth d.
// 2) 答案是 2^(d-1) mod 1e9+7（路徑上選奇數條邊為權重 1 的方法數）。
//    Answer is 2^(d-1) mod 1e9+7, the number of ways to pick an odd subset of d edges.

#define MOD 1000000007L  // 取模常數 / the modulus 10^9 + 7

// 快速冪：在 O(log e) 時間算出 base^e mod MOD。
// Fast exponentiation: computes base^e mod MOD in O(log e).
long power(long base, long e) {
    long result = 1;                 // 累積結果，從 1 開始 / running product, starts at 1
    base %= MOD;                     // 先取模，避免 base 過大 / reduce base mod MOD first
    while (e > 0) {                  // 逐個處理指數的二進位位元 / process each bit of the exponent
        if (e & 1)                   // 若當前最低位是 1（e 為奇數）/ if the lowest bit is set
            result = result * base % MOD;  // 把這個 base 的次方乘進結果 / fold this power into result
        base = base * base % MOD;    // base 平方，對應下一個位元 / square base for the next bit
        e >>= 1;                     // 指數右移一位 / shift exponent right by one bit
    }
    return result;
}

int assignEdgeWeights(int** edges, int edgesSize, int* edgesColSize) {
    int n = edgesSize + 1;           // 樹有 n 個節點，邊數 = n-1 / n nodes, since edges = n-1

    // ---- 建立鄰接表 / Build adjacency list ----
    // adjCount[u] 記錄節點 u 有幾個鄰居 / number of neighbors of node u
    int* adjCount = (int*)calloc(n + 1, sizeof(int));  // calloc 會把記憶體清為 0 / calloc zeroes memory
    for (int i = 0; i < edgesSize; i++) {  // 先數每個節點的鄰居數 / first count neighbors per node
        adjCount[edges[i][0]]++;     // 邊的一端 +1 / one endpoint
        adjCount[edges[i][1]]++;     // 另一端 +1（無向邊雙向）/ the other endpoint (undirected)
    }

    // adj[u] 是一個動態陣列，存節點 u 的所有鄰居 / adj[u] holds u's neighbors
    int** adj = (int**)malloc((n + 1) * sizeof(int*));  // 指標陣列 / array of pointers
    int* idx = (int*)calloc(n + 1, sizeof(int));        // 每個 u 目前已填入幾個鄰居 / fill position per node
    for (int u = 1; u <= n; u++)
        adj[u] = (int*)malloc(adjCount[u] * sizeof(int));  // 為每個節點配置剛好夠用的空間 / exact-size buffer
    for (int i = 0; i < edgesSize; i++) {  // 第二趟：真正填入鄰居 / second pass: fill neighbors
        int u = edges[i][0], v = edges[i][1];
        adj[u][idx[u]++] = v;        // 把 v 加到 u 的清單，idx[u] 後移 / append v to u, advance write index
        adj[v][idx[v]++] = u;        // 把 u 加到 v 的清單 / append u to v
    }

    // ---- BFS 求最大深度 / BFS to find max depth ----
    int* depth = (int*)malloc((n + 1) * sizeof(int));   // 每個節點的深度 / depth of each node
    char* visited = (char*)calloc(n + 1, sizeof(char)); // 標記是否已走訪，避免回頭 / visited flag
    int* queue = (int*)malloc(n * sizeof(int));         // 用陣列當佇列 / array used as a queue
    int head = 0, tail = 0;          // head 指向待取出位置，tail 指向待寫入位置 / read/write cursors

    queue[tail++] = 1;               // 從根節點 1 開始 / start BFS at root node 1
    visited[1] = 1;                  // 標記根已走訪 / mark root visited
    depth[1] = 0;                    // 根的深度為 0 / root depth is 0
    int maxDepth = 0;                // 目前看到的最大深度 / max depth seen so far

    while (head < tail) {            // 佇列還有節點就繼續 / while queue is not empty
        int u = queue[head++];       // 取出隊首節點 / dequeue front node
        if (depth[u] > maxDepth)     // 更新最大深度 / update the maximum depth
            maxDepth = depth[u];
        for (int j = 0; j < adjCount[u]; j++) {  // 走訪 u 的每個鄰居 / iterate neighbors of u
            int w = adj[u][j];
            if (!visited[w]) {       // 沒走訪過才處理（樹不會有環，但仍要防回到父節點）/ skip the parent
                visited[w] = 1;      // 標記已走訪 / mark visited
                depth[w] = depth[u] + 1;  // 子節點深度 = 父深度 + 1 / child depth = parent + 1
                queue[tail++] = w;   // 加入佇列 / enqueue child
            }
        }
    }

    // ---- 釋放記憶體 / Free memory ----
    for (int u = 1; u <= n; u++) free(adj[u]);  // 釋放每個鄰居清單 / free each neighbor list
    free(adj); free(adjCount); free(idx);
    free(depth); free(visited); free(queue);

    // 答案 = 2^(maxDepth - 1) mod 1e9+7 / answer = 2^(maxDepth-1)
    return (int)power(2, maxDepth - 1);
}