좋은 경로의 세 쌍

노드가 $N$개인 트리가 주어진다. 서로 다른 두 노드를 잇는 단순 경로의 개수를 $M$이라고 하면 $M = N(N-1)/2$이다.

단순 경로 세 개를 순서 없이 고르는 방법은 모두 $M(M-1)(M-2)/6$가지다. 세 경로 $(A, B, C)$가 다음 두 조건 중 적어도 하나를 만족하면 좋은 경로의 세 쌍이라고 한다.

• 세 경로 $A$, $B$, $C$가 모두 서로 다른 노드로 이루어져 있다. 즉 어느 두 경로도 노드를 공유하지 않는다.
• 세 경로가 모두 교차한다. 즉 $A$와 $B$가 노드를 적어도 하나 공유하고, $A$와 $C$도, $B$와 $C$도 노드를 적어도 하나 공유한다.

트리가 주어졌을 때 좋은 경로의 세 쌍이 몇 개인지 구하는 프로그램을 작성하시오.

첫째 줄에 $N$ ($4 \le N \le 300{,}000$)이 주어진다.

둘째 줄부터 $N-1$개의 줄에 트리의 간선을 이루는 두 정점의 번호가 주어진다. 정점 번호는 $1$번부터 $N$번까지다.

좋은 경로의 세 쌍의 개수를 $10^9+7$로 나눈 나머지를 출력한다.

경로를 양 끝 정점으로 적으면, 노드가 $4$개이고 간선이 $1$과 $2$, $2$와 $3$, $3$과 $4$를 잇는 트리에서 좋은 경로의 세 쌍은 다음 $16$개다.

• $(1, 2)$, $(1, 3)$, $(1, 4)$
• $(1, 2)$, $(1, 3)$, $(2, 3)$
• $(1, 2)$, $(1, 3)$, $(2, 4)$
• $(1, 2)$, $(1, 4)$, $(2, 3)$
• $(1, 2)$, $(1, 4)$, $(2, 4)$
• $(1, 2)$, $(2, 3)$, $(2, 4)$
• $(1, 3)$, $(1, 4)$, $(2, 3)$
• $(1, 3)$, $(1, 4)$, $(2, 4)$
• $(1, 3)$, $(1, 4)$, $(3, 4)$
• $(1, 3)$, $(2, 3)$, $(2, 4)$
• $(1, 3)$, $(2, 3)$, $(3, 4)$
• $(1, 3)$, $(2, 4)$, $(3, 4)$
• $(1, 4)$, $(2, 3)$, $(2, 4)$
• $(1, 4)$, $(2, 3)$, $(3, 4)$
• $(1, 4)$, $(2, 4)$, $(3, 4)$
• $(2, 3)$, $(2, 4)$, $(3, 4)$