問題文

以下の性質を持つ有向グラフを Chain Graph と呼ぶことにします。

• 相異なる頂点 i, j, k について、 i \rightarrow j と j \rightarrow k の辺があるとき、i \rightarrow k の辺も存在する。
• 無向グラフとしてみたときに、自己ループや多重辺が存在しない。

無向辺からなる N 頂点の完全グラフが与えられます。頂点には 1 から N の番号がついています。はじめ、N-1 本の辺が赤で塗られており、木をなしています。i 番目の赤色の辺は A_i と B_i を結ぶ辺です。残りの辺は白色です。

あなたは、以下の操作を順番に行い、グラフの辺の色と向きを定めます。

• 全ての白色の辺をそれぞれ赤色、または青色に塗る。
• 全ての赤色の辺、青色の辺それぞれに向きをつける。

赤色、青色それぞれの辺のみからなるグラフが Chain Graph となるような操作後のグラフとしてありえるものの数を 998244353 で割ったあまりを求めてください。

制約

• 入力は全て整数
• 1 \le N \le 100
• 1 \le A_i, B_i \le N
• 与えられる赤色の辺からなるグラフは木である

入力例 1

3
1 2
2 3

出力例 1

10

以下の二つのグラフがありうるグラフの一例です。

入力例 2

5
1 2
1 3
2 4
5 2

出力例 2

1304

以下のようなグラフが考えられます。

入力例 3

10
1 2
1 3
4 2
2 5
3 6
6 7
8 7
9 5
5 10

出力例 3

793075136

答えを 998244353 で割った余りを出力してください。