如你所知，树是一个由 $n$ 个节点和 $n - 1$ 条无向边组成的图，其中任意两个节点之间恰好有一条路径。在标记树中，每个节点都被赋予一个 $1$ 到 $n$ 之间的不同整数。通常情况下，树可能很难直观地呈现，但有些树可以整齐地嵌入到矩形网格中。

给定一棵有 $n$ 个节点的标记树 $G$，树 $G$ 的 $2 \times n$ 嵌入是指将 $G$ 的节点映射到由 $2$ 行 $n$ 列组成的矩形网格单元格中，并满足以下条件：

• 节点 $1$ 映射到左上角的单元格。
• 有边相连的节点映射到相邻的网格单元格（上、下、左或右）。
• 没有两个节点映射到同一个单元格。

求给定树的 $2 \times n$ 嵌入数量，结果对 $10^9 + 7$ 取模。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 300\,000$)，表示 $G$ 中的节点数。接下来的 $n - 1$ 行中，第 $j$ 行包含两个不同的整数 $a_j$ 和 $b_j$ ($1 \le a_j, b_j \le n$)，表示第 $j$ 条边的两个端点。

输出格式

输出给定树的 $2 \times n$ 嵌入数量，结果对 $10^9 + 7$ 取模。

样例

样例输入 1

5
1 2
2 3
2 4
4 5

样例输出 1

4

说明

样例输入中树的所有 4 种嵌入方式如上图所示。