問題文

青木くんは 頂点$1,2,...,N$ からなる根付き木 $T$ を手に入れました。$T$ の根は頂点$1$ です。
青木くんは根付き木 $T$ の各頂点に $1,2,...,N$ の値を重複無く書き込む事を考えています。
つまり頂点$i$ に書き込まれた値を $c_i$ とするとき、 数列$\{c_i\}$ が $\{1,2,...,N\}$ の順列であるようにします。

青木くんは、「頂点$i$ に、頂点$i$の(自分を除く)どの先祖の値よりも大きな値が書き込まれている」とき、頂点$i$ を神童と呼ぶことに決めました。但し根は必ず神童であるとします。
また $N$頂点のうち、いくつが神童であるかを神童数と定義しました。
例えば下図のような値の書き込み方を考えると、黄色の頂点が神童であり、神童数は4となります。
ここで $6$の値が書き込まれた頂点は神童です。なぜなら先祖に$\{3,1\}$の値が書き込まれており、$6$未満の値しか含まれないからです。
また $4$の値が書き込まれた頂点は神童ではありません。なぜなら先祖に$\{3,7\}$の値が書き込まれており、$4$よりも大きな値が含まれるからです。

青木くんは根付き木$T$ がいかに優秀な木か気になり、 値の書き込み方$N!$ 通り全てを試した場合に神童数の合計はいくつになるか尋ねてきました。
あなたの仕事はこの答えを青木くんの代わりに計算することです。 但しこの値は非常に大きくなりうるので、${10}^9+7$ で割った余りで教えてあげて下さい。

入力

$N$ 
$u_1{v}_1$
$u_2{v}_2$
$⋮$
$u_{N-1}{v}_{N-1}$

１行目に木の頂点数$N$ が与えられます。
２行目から$N$行目までには、木$T$ の辺の端点を表す整数 $u,v$ が空白区切りで与えられます。これは頂点$u,v$が双方向に結ばれていることを意味します。

制約

• $1\le N\le 2\times {10}^5$
• $1\le u_i,v_i\le N$
• 入力されるグラフは$N$頂点の木である。
• 入力は全て整数である。

出力

$T$への値の書き込み方$N!$通り全てに対する、神童数の総和を${10}^9+7$で割った余りを一行に出力して下さい。
最後に改行して下さい。

サンプル

サンプル1

入力サンプルをコピー

入力

2
1 2

出力

3

値の書き込み方は以下の２通りあり、黄色の頂点が神童です。
右で１が書かれた頂点は、親の値が２であり自分の値より大きいので神童ではありません。

サンプル2

入力サンプルをコピー

入力

3
1 2
2 3

出力

11

値の書き込み方は以下の６通りあり、黄色の頂点が神童です。

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

820010006