2 × n 격자 임베딩의 개수

트리는 정점 $n$개와 무방향 간선 $n-1$개로 이루어진 그래프이고, 어떤 두 정점 사이에도 경로가 정확히 하나 있다. 라벨 트리는 정점마다 1 이상 $n$ 이하의 정수가 서로 다르게 하나씩 붙은 트리다. 트리를 보기 좋게 그리기는 대체로 어렵지만, 직사각형 격자에 깔끔하게 담기는 트리도 있다.

정점이 $n$개인 라벨 트리 $G$가 있다. $G$의 $2 \times n$ 임베딩은 $G$의 정점을 2행 $n$열 격자의 칸에 대응시키는 함수이고, 다음 세 조건을 모두 만족한다.

• 정점 1은 왼쪽 위 모서리 칸에 대응한다.
• 간선으로 이어진 두 정점은 위, 아래, 왼쪽, 오른쪽으로 맞닿은 두 칸에 대응한다.
• 서로 다른 두 정점은 같은 칸에 대응하지 않는다.

주어진 트리의 $2 \times n$ 임베딩 개수를 $10^9 + 7$로 나눈 나머지를 구하라.

첫째 줄에 $G$의 정점 개수 $n$이 주어진다. ($1 \le n \le 300\,000$)

이어지는 $n-1$개 줄 중 $j$번째 줄에는 $j$번째 간선의 두 끝점 $a_j$와 $b_j$가 주어진다. ($1 \le a_j, b_j \le n$, $a_j \ne b_j$)

입력으로 주어지는 그래프는 항상 트리다.

주어진 트리의 $2 \times n$ 임베딩 개수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.

위 그림은 첫 번째 예제에 주어진 트리의 임베딩 4개를 모두 그린 것이다.