All Even

頂点の木 が与えられます。各頂点には から の番号が付いており、 番目の辺は頂点 と を双方向に結んでいます。
長さ の順列 であって、以下の条件を満たすものの個数を で割った余りを求めてください。

• をともに満たす全ての正整数の組 について、 が偶数である。

ただし、 は の頂点 から頂点 への最短経路に存在する辺の本数を表します。

• 入力は全て整数
• 与えられるグラフは木である 　　

入力は以下の形式で標準入力から与えられます。

答えを出力してください。

3
1 2
1 3

2

として考えられるものは つありますが、そのうち と の つが条件を満たします。

23
20 7
12 1
3 1
4 16
7 12
6 2
22 9
2 15
5 16
14 16
4 18
10 11
3 10
3 13
21 14
8 6
16 8
9 12
4 3
2 17
19 17
23 22

445103186

答えを で割った余りを求めてください。