Background

维系者正在死去，创造者尚未到来。

但世界不会再度灼烧，因为你将登上「神」之座。

-------------------------------------------------------------------------------------------

陌生的天空下，少年少女立于尘沙。

你们是一对旅行中的双子，远渡重天，曾经跨越诸多世界。

在降临名为「提瓦特」的大陆之前，你希望能与这个世界相处愉快。

然而当你从陨星中复苏，却见到天变地异、灾祸横行——

你们想要离开这里、前往下一个世界······

但此时有陌生的神灵出现，拦在你们面前。

一尘不染的神，漂浮在浊世的天空。

俯视着你。

神带走了你唯一的血亲，而你也被神封印，陷入充满噩梦的沉眠······

再度醒来，天地间风景已变。

眼前已不再有战火，也不再有任何熟悉的景象。

自己究竟又沉睡了多少年？这也无从知晓。

于是你孤身一人踏上旅途，去寻找曾经目睹的神灵······

Description

你是荧(空)，提瓦特大陆上的旅行者。

据知情人士透露(指喝醉后的巴巴托斯)，即将开放的草国「须弥」构成树形结构，其上有若干条有向道路。作为经验丰富的旅行者，你自然不愿意在曾经走过的道路上浪费时间，于是你决定选择尽可能多的两两不交的道路完成你的旅行，并用走过的道路数量来刻画这次旅行的愉悦程度。请注意，任意一条道路可以被一个有序点对 (u, v) 刻画，它表示树上 u 到 v 的最短路径。

遗憾的是，由于巴巴托斯酒喝多了，并未详细地告诉你须弥的道路建设情况，于是你决定求出所有道路建设情况下旅行愉悦度的总和。

第一行一个正整数数 ，表示树的结点数。
接下来  行，每行两个正整数，描述树上的一条边。

一个数，表示答案对  取模后的值。

3
1 2
1 3

927

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

434455072

保证 。



- 一个点也算一条路径。

- 两条路径相交当且仅当它们存在公共点。