Busy Beaver 又在農夫市場製造混亂了！這一次，他在攤位之間發起了一場食物大戰。

這些攤位編號為 $1$ 到 $N$，並由 $N - 1$ 條道路連接，形成一棵樹。換句話說，可以透過這些道路從任何一個攤位前往另一個攤位，且任意兩個攤位之間恰好有一條簡單路徑。

Busy Beaver 依照下列規則將每個攤位分配給「馬鈴薯隊 (Team Potato)」或「番茄隊 (Team Tomato)」：

• 他從攤位 $1$ 出發，沿著道路行走，造訪每一個攤位，最後回到攤位 $1$。在所有這類路徑中，他選擇一條總路徑長度（經過道路的總次數）最小的路徑。
• 攤位 $1$ 被分配給馬鈴薯隊。
• 每當 Busy Beaver 第一次造訪某個攤位（攤位 $1$ 除外）時，他會立即將其分配給其中一個隊伍。為了保持公平，他每次分配新攤位時都會交替隊伍。也就是說，如果最近一次被分配的攤位屬於馬鈴薯隊，那麼下一個新造訪的攤位必須分配給番茄隊，反之亦然。

你的任務是計算可能的隊伍分配方案數量。請注意，不同的最小長度路徑可能會產生相同的最終分配結果；這類分配方案應只計算一次。由於答案可能非常巨大，請輸出其對 $10^9 + 7$ 取模後的結果。

輸入格式

第一行包含一個整數 $T$ ($1 \le T \le 10^4$)，代表測試案例的數量。

每個測試案例的第一行包含一個整數 $N$ ($2 \le N \le 10^5$)。

接下來的 $N - 1$ 行，每行包含兩個整數 $u$ 和 $v$ ($1 \le u, v \le N, u \neq v$)，表示攤位 $u$ 和 $v$ 之間有一條道路。

所有測試案例的 $N$ 總和不超過 $2 \cdot 10^5$。

輸出格式

對於每個測試案例，輸出一個整數：可能的最終隊伍分配方案數量，對 $10^9 + 7$ 取模。

子任務

本題共有兩個子任務：

• (10 分)：攤位形成以攤位 $1$ 為根的星狀圖。更具體地說，攤位 $1$ 連接了 $N - 1$ 條道路。
• (20 分)：攤位形成以攤位 $1$ 為根的二元樹。更具體地說，攤位 $1$ 最多連接 $2$ 條道路，且其他每個攤位最多連接 $3$ 條道路。
• (70 分)：無額外限制。

範例

輸入 1

4
4
1 2
2 3
2 4
7
1 2
1 3
1 4
1 5
1 6
1 7
7
1 2
1 3
2 4
2 5
3 6
3 7
7
1 2
1 3
1 4
2 5
2 6
2 7

輸出 1

2
20
8
12

說明

範例包含 4 個測試案例：

• 測試案例 1 滿足第二個子任務（二元樹）。
• 測試案例 2 滿足第一個子任務（星狀圖）。
• 測試案例 3 滿足第二個子任務（二元樹）。
• 測試案例 4 滿足第三個子任務（無額外限制）。

在第一個測試案例中，其中一種可能的隊伍分配如下所示。

其中一條最小長度路徑為： $1 \to 2 \to 3 \to 2 \to 4 \to 2 \to 1$。

其總長度為 $6$，這是從攤位 $1$ 出發、造訪所有攤位並回到攤位 $1$ 的路徑中最小的長度。

攤位依照第一次造訪的順序進行分配： 攤位 $1$ 分配給馬鈴薯隊。 攤位 $2$ 分配給番茄隊。 攤位 $3$ 分配給馬鈴薯隊。 攤位 $4$ 分配給番茄隊。

另一種可能的隊伍分配是透過在造訪攤位 $3$ 之前先造訪攤位 $4$ 獲得，這會交換它們的隊伍。因此，可能的隊伍分配總數為 $2$。