完全二分木とは、すべての非葉ノードがちょうど2つの子を持ち、すべての葉ノードが根から等距離にある根付き木のことである。
根なし完全二分木とは、あるノードを根としたときに完全二分木となるような根なし木のことである。
Bessieは $N$ ($1 \le N \le 10^5$) 個のノードを持つ木を持っている。この木から辺の集合をいくつか取り除き、残った森が根なし完全二分木の集合となるような取り除き方の総数を求めよ。答えは非常に大きくなる可能性があるため、$10^9+7$ で割った余りを出力せよ。
入力
最初の行には、独立したテストケースの数 $T$ ($1 \leq T \leq 100$) が含まれる。
各テストケースの最初の行には、整数 $N$ が含まれる。
続く $N-1$ 行の各行には、ノード $u_i$ と $v_i$ ($1 \leq u_i, v_i \leq N$) を結ぶ辺を表す2つの整数が含まれる。
各テストケースにおいて、与えられた辺が $N$ 個のノードからなる木を形成することが保証されている。
さらに、すべてのテストケースにおける $N$ の総和は $2\cdot 10^5$ を超えない。
出力
各テストケースについて、辺を取り除いた結果が根なし完全二分木の森となるような辺の集合の数を、$10^9+7$ で割った余りとして1行に出力せよ。
入出力例
入力 1
3 6 1 2 3 2 4 6 5 6 6 2 3 1 2 3 2 7 2 1 2 3 1 6 1 7 3 4 3 5
出力 1
8 2 14
注記
最初のテストケースにおいて、Bessieは以下のいずれかの辺の集合を取り除くことで、完全二分木の森を得ることができる：
- $(2, 6)$
- $(1, 2)$, $(2, 3)$, $(2, 6)$
- $(1, 2)$, $(2, 3)$, $(4, 6)$
- $(1, 2)$, $(2, 3)$, $(5, 6)$
- $(1, 2)$, $(4, 6)$, $(5, 6)$
- $(2, 6)$, $(4, 6)$, $(5, 6)$
- $(2, 3)$, $(4, 6)$, $(5, 6)$
- $(1, 2)$, $(2, 3)$, $(2, 6)$, $(4, 6)$, $(5, 6)$
1番目の集合を取り除くと高さ $1$ の部分木が2つ得られ、最後の集合を取り除くと高さ $0$ の部分木が6つ得られる。その他の集合を取り除くと、高さ $0$ の部分木が3つと高さ $1$ の部分木が1つ得られる。
小課題
- 入力 2-3: $N\le 15$
- 入力 4-5: どのノードも他の3つ以上のノードと隣接していない。
- 入力 6-9: $N\le 1000$、すべての $N$ の総和は $2000$ を超えず、どのノードも他の4つ以上のノードと隣接していない。
- 入力 10-13: どのノードも他の4つ以上のノードと隣接していない。
- 入力 14-21: 追加の制約はない。
問題作成者: Avnith Vijayram