Embedding Enumeration

Time limit4sMemory limit512 MB

Summary

Count the ways to place a labeled tree's nodes into a 2 by n grid so node 1 sits at the top-left, edges touch, and no cell repeats, modulo 1e9+7.

Level: Hard8 of 10
Topics: Tree, DFS, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

A tree is a graph with $n$ nodes and $n-1$ undirected edges in which every two nodes are joined by exactly one path. In a labeled tree every node carries a different integer between 1 and $n$ . Drawing a tree neatly is hard in general, but some trees fit into a rectangular grid.

Let $G$ be a labeled tree with $n$ nodes. A $2 \times n$ embedding of $G$ maps the nodes of $G$ to the cells of a grid with 2 rows and $n$ columns so that all three conditions hold.

Node 1 maps to the cell in the upper left corner.
Two nodes joined by an edge map to two cells that touch up, down, left or right.
No two nodes map to the same cell.

Count the $2 \times n$ embeddings of the given tree, modulo $10^9 + 7$ .

Input

The first line contains the number of nodes $n$ of $G$ ( $1 \le n \le 300\,000$ ).

The $j$ -th of the next $n-1$ lines contains the two endpoints $a_j$ and $b_j$ of the $j$ -th edge ( $1 \le a_j, b_j \le n$ , $a_j \ne b_j$ ).

The given graph is always a tree.

Output

Print the number of $2 \times n$ embeddings of the given tree, modulo $10^9 + 7$ .

Note

The figure above draws all 4 embeddings of the tree in the first example.

Examples3

Example 1
Input
```
5
1 2
2 3
2 4
4 5
```
Expected output
```
4
```
Example 2
Input
```
1
```
Expected output
```
1
```
Example 3
Input
```
2
2 1
```
Expected output
```
2
```