頂点の木 が与えられます。各頂点には から の番号が付いており、 番目の辺は頂点 と を双方向に結んでいます。
長さ の順列 であって、以下の条件を満たすものの個数を で割った余りを求めてください。
ただし、 は の頂点 から頂点 への最短経路に存在する辺の本数を表します。
入力は以下の形式で標準入力から与えられます。
答えを出力してください。
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
答えを で割った余りを求めてください。