트리의 모든 연결 부분그래프를 세고, 각 부분그래프의 정점 수 합을 1e9+7로 나눈 나머지를 구한다.
양방향 트리 TTT가 주어진다. 트리의 정점에는 000번부터 N−1N-1N−1번까지 번호가 붙어 있다.
TTT의 서브 트리는 정점을 하나 이상 포함하는 TTT의 연결된 부분 그래프를 뜻한다. 서브 트리의 크기는 그 안에 들어 있는 정점의 개수이다.
TTT의 모든 서브 트리의 크기를 더한 값을 구하는 프로그램을 작성하시오.
첫째 줄에 정점의 개수 NNN이 주어진다. (1≤N≤1051 \le N \le 10^51≤N≤105)
다음 N−1N-1N−1개의 줄에 트리의 간선이 한 줄에 하나씩 주어진다. 각 줄에는 간선으로 이어진 두 정점의 번호 uuu와 vvv가 주어진다. (0≤u,v≤N−10 \le u, v \le N-10≤u,v≤N−1, u≠vu \ne vu=v)
주어지는 간선은 항상 트리를 이룬다.
첫째 줄에 모든 서브 트리의 크기의 합을 1,000,000,007로 나눈 나머지를 출력한다.