33972번 - g-raph 신앙 (Hard)

문제

고고학자들의 연구에 따르면 토속 신앙 토테미즘 중에는 기린을 숭배하는 g-raph 신앙이 존재했다. 이들은 상징으로 그래프를 사용하였으며, 트리야말로 완벽한 그래프라 생각하여 마을에 정점이 $N$개인 거대한 트리상을 세우고 매일 기도하는 시간을 가졌다.

천둥이 울리던 어느 날, g-raph가 강림하여 다음의 마술을 부렸다.

• 먼저 트리상의 간선 $N-1$개 중 하나를 균일한 확률로 선택하여 없앤다.
• 다음으로 간선이 존재하지 않는 정점 쌍 중 하나를 균일한 확률로 선택하여 이 두 정점을 잇는 간선을 하나 생성한다.

심지어 이를 두 번 하고 떠났다. 마을 사람들은 첫 번째 마술이 끝난 직후와 두 번째 마술이 끝난 직후 모두 트리상의 트리 조건이 한 번도 위배되지 않았다는 것을 보고 이를 축복이라 여겼다.

이에 감명 받은 마을의 수학자는 이 확률이 얼마일지 계산해 보게 된다. 얼마일까?

입력

첫째 줄에 트리상에 존재하는 정점의 개수 $N$이 주어진다. $(2 \leq N \leq 200,000円)$

둘째 줄부터 $N-1$개의 줄에 걸쳐 트리상에 존재하는 간선의 정보가 한 줄에 하나씩 주어진다. 각 줄에는 $u_i,ドル $v_i$가 공백으로 구분되어 주어지며, 이는 $u_i$번 정점과 $v_i$번 정점이 간선으로 연결되어 있다는 의미이다. $(1 \leq u_i, v_i \leq N)$

입력으로 주어지는 모든 수는 정수이다.

출력

첫째 줄에 수학자가 계산한 확률을 998ドル,244円,353円$으로 나눈 나머지를 출력한다.

기약 분수 $\frac{p}{q}$를 $M$으로 나눈 나머지는 $q^{-1}$이 $q \cdot q^{-1} \equiv 1 \pmod{M}$을 만족하는 정수일 때, $p \cdot q^{-1} \pmod{M}$으로 정의한다.

분모가 998ドル,244円,353円$의 배수인 기약 분수가 정답이라면 -1을 출력한다.

제한

노트

간선을 지운 다음 간선이 존재하지 않는 정점 쌍 사이에 생성하는 것이기 때문에, 지운 위치에 다시 간선이 생성될 수 있다.