Counting 2 by n Tree Embeddings

Given a labeled tree \(G\) with \(n\) nodes and \(n-1\) undirected edges, a 2 by n embedding of \(G\) is a mapping of its nodes to the cells of a rectangular grid of 2 rows and \(n\) columns satisfying:

• Node \(1\) is mapped to the cell in the upper-left corner.
• If two nodes are connected by an edge, then their corresponding cells in the grid must be adjacent (neighbors in the up, down, left, or right direction).
• No two nodes are mapped to the same cell.

Determine the number of valid embeddings modulo \(10^9+7\).

inputFormat

The first line contains an integer \(n\) representing the number of nodes. The following \(n-1\) lines each contain two integers \(u\) and \(v\) (\(1 \le u,v \le n\)), denoting an edge connecting nodes \(u\) and \(v\).

outputFormat

Output a single integer: the number of valid 2 by n embeddings of the given tree modulo \(10^9+7\).

sample

1

1