시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 15 | 8 | 6 | 46.154% |
As you probably know, a tree is a graph consisting of n nodes and n − 1 undirected edges in which any two nodes are connected by exactly one path. In a labeled tree each node is labeled with a different integer between 1 and n. In general, it may be hard to visualize trees nicely, but some trees can be neatly embedded in rectangular grids.
Given a labeled tree G with n nodes, a 2 by n embedding of G is a mapping of nodes of G to the cells of a rectangular grid consisting of 2 rows and n columns such that:
Find the number of 2 by n embeddings of a given tree, modulo 109 + 7.
The first line contains an integer n (1 ≤ n ≤ 300 000) — the number of nodes in G. The j-th of the following n − 1 lines contains two different integers aj and bj (1 ≤ aj, bj ≤ n) — the endpoints of the j-th edge.
Output the number of 2 by n embeddings of the given tree, modulo 109 + 7.
5 1 2 2 3 2 4 4 5
4
All 4 embeddings of the tree in the example input are given in the figure above.