Busy Beaver が再びファーマーズマーケットで大混乱を引き起こしています！今回、彼は屋台の間でフードファイトを始めようとしています。

屋台には $1$ から $N$ までの番号が振られており、$N-1$ 本の道路で結ばれていて木を形成しています。言い換えれば、どの屋台からどの屋台へも道路をたどって移動することが可能であり、任意の2つの屋台間には唯一の単純パスが存在します。

Busy Beaver は、各屋台を次のように「チーム・ポテト」または「チーム・トマト」のいずれかに割り当てます。

• 彼は屋台 $1$ から出発し、道路をたどってすべての屋台を訪れ、最後に屋台 $1$ に戻ります。そのようなすべてのルートの中で、彼は移動する道路の総数が最小となるルートを1つ選択します。
• 屋台 $1$ は「チーム・ポテト」に割り当てられます。
• Busy Beaver が（屋台 $1$ 以外の）屋台を初めて訪れるたびに、彼は直ちにその屋台を2つのチームのいずれかに割り当てます。公平を期すため、彼は新しい屋台を割り当てるたびにチームの割り当てを交互に入れ替えます。つまり、直前に割り当てられた屋台が「チーム・ポテト」であった場合、次に新しく訪れた屋台は「チーム・トマト」に割り当てられ、その逆も同様です。

あなたの課題は、可能なチーム割り当ての数を数えることです。異なる最小長のルートが同じ最終割り当てを生み出す可能性があることに注意してください。そのような割り当ては1回のみカウントする必要があります。答えは非常に大きくなる可能性があるため、$10^9 + 7$ で割った余りを出力してください。

入力

入力の最初の行には、テストケースの数 $T$ ($1 \le T \le 10^4$) が含まれます。

各テストケースの最初の行には、整数 $N$ ($2 \le N \le 10^5$) が含まれます。

続く $N-1$ 行の各行には、2つの整数 $u$ と $v$ ($1 \le u, v \le N, u \neq v$) が含まれており、屋台 $u$ と $v$ の間に道路があることを示しています。

すべてのテストケースにおける $N$ の合計は $2 \cdot 10^5$ を超えません。

出力

各テストケースについて、可能な最終チーム割り当ての数を $10^9 + 7$ で割った余りを1つの整数で出力してください。

小課題

この問題には2つの小課題があります。

• (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番目の小課題（二分木）を満たします。
• テストケース 2 は1番目の小課題（スターグラフ）を満たします。
• テストケース 3 は2番目の小課題（二分木）を満たします。
• テストケース 4 は3番目の小課題（追加の制約なし）を満たします。

最初のテストケースにおいて、可能なチーム割り当ての1つを以下に示します。

最小長のルートの1つは以下の通りです： $1 \to 2 \to 3 \to 2 \to 4 \to 2 \to 1$

その全長は $6$ であり、これは屋台 $1$ から出発し、すべての屋台を訪れ、屋台 $1$ に戻るルートとして最小のものです。

屋台は、最初に訪れた順序で割り当てられます：

• 屋台 $1$ は「チーム・ポテト」に割り当てられます。
• 屋台 $2$ は「チーム・トマト」に割り当てられます。
• 屋台 $3$ は「チーム・ポテト」に割り当てられます。
• 屋台 $4$ は「チーム・トマト」に割り当てられます。

もう1つの可能なチーム割り当ては、屋台 $3$ より先に屋台 $4$ を訪れることで得られ、これによりチームが入れ替わります。したがって、可能なチーム割り当ての総数は $2$ です。