問題文


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

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

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

  

制約


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

入力


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





  

出力


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

  

入力例1


3
1 2
1 3

出力例1


2

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

入力例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

出力例2


445103186

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

Submit


Go (1.14)