Embedding Enumeration

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$.

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.

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

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