Background

首先是最近公共祖先的概念(什么是最近公共祖先？)

在一棵没有环的树上，每个节点肯定有其父亲节点和祖先节点，而最近公共祖先，就是两个节点在这棵树上深度最大的公共的祖先节点。

换句话说，就是两个点在这棵树上距离最近的公共祖先节点。

所以LCA主要是用来处理当两个点仅有唯一一条确定的最短路径时的路径。

Description

Alpha已经学会了如何快速求LCA。

给定一棵树，\(N\)个节点，\(N-1\)条边串联，第\(i\)条边连接\(u_i\)和\(v_i\)，根节点为1。

定义一个函数: \(LCA(i,j)\)，其值为\(i\)和\(j\)的最近公共祖先的点编号。

试求表达式\(\overset{N-1}{\underset{i=1}{\sum}}\overset{N}{\underset{j=i+1}{\sum}}LCA(i,j)\)的值，答案对\(998244353\)取余。

Format

Input

第\(1\)行一个整数\(N\)，表示树的大小。

第\(2\)行至第\(N\)行，每行两个整数，描述一条边。

可以认为一条边的输入为\(dad\)节点和\(son\)节点

Output

第\(1\)行一个整数，表示表达式的值。

Sample 1

Input

6
1 2
2 3
3 4
3 5
4 6

Output

32

Sample 2

Input

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

Output

520

Limitation

对于\(100\%\)的数据: \(2\leq N\leq 10^6,1\leq u_i,v_i\leq N\)

Hint

No Hint