Vasya 拥有一个无穷大的二叉树 $T$，其形式化描述如下：$T$ 有无穷多个顶点，编号从 1 开始。每个顶点都有两个子节点——左儿子和右儿子。顶点 $i$ 的左儿子是顶点 $2i$，右儿子是顶点 $2i + 1$。

此外，Vasya 还有另一个二叉树 $G$（幸运的是，它是有限的）。$G$ 的每个顶点要么是内部节点，要么是叶子节点。内部节点有一个左儿子和一个右儿子（被称为其子节点的父节点），而叶子节点没有子节点。每个顶点恰好有一个父节点，只有一个顶点除外，它没有父节点；这个顶点被称为树 $G$ 的根。

Vasya 想要将树 $G$ 嵌入到无穷大树 $T$ 中。形式上，嵌入被定义为一个函数 $f : V(G) \to V(T)$（其中 $V(X)$ 是树 $X$ 的顶点集），满足以下性质：如果顶点 $v$ 是 $G$ 中顶点 $u$ 的左（或右）儿子，则顶点 $f(v)$ 必须位于 $T$ 中顶点 $f(u)$ 的左（或右）儿子的子树内。

非正式地说，嵌入是将 $G$ 的顶点放置在 $T$ 上的方式，使得如果我们连接所有嵌入的顶点与其子节点，绘制出的图形看起来就像 $G$，且某些边可能向下延伸（查看样例的图片有助于更好地理解这一概念）。

此外，对于每个叶子节点 $v$，Vasya 选择了一个数字 $h_v$——即 $v$ 所嵌入的 $T$ 中顶点的高度（顶点的高度是指该顶点与树根之间的边数）。也就是说，对于树 $G$ 的每个叶子 $v$，必须满足 $\text{height}(f(v)) = h_v$。

现在，Vasya 想知道 $G$ 在 $T$ 中满足每个叶子 $v$ 都嵌入到高度为 $h_v$ 的顶点的不同嵌入方案数。由于数量可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $n$ —— $G$ 的顶点数 ($1 \le n \le 2000$)。

接下来的 $n$ 行描述了树 $G$ 以及数字 $h_v$。

如果第 $i$ 个顶点是内部节点，则该行的第一个数字为 0，后面依次是其左儿子和右儿子的编号。

如果第 $i$ 个顶点是叶子节点，则该行的第一个数字为 1，后面是该叶子的高度 $h_i$。所有 $h_i$ 满足 $0 \le h_i \le 10^9$。

保证 $G$ 的根是顶点 1。

输出格式

输出一个整数 —— 合法嵌入方案数对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

3
0 2 3
1 2
1 2

样例输出 1

6

样例输入 2

5
0 2 3
0 4 5
1 2
1 3
1 3

样例输出 2

14

样例输入 3

3
0 2 3
1 0
1 0

样例输出 3

0

样例输入 4

1
1 0

样例输出 4

1

说明

第一个样例的所有六种可能嵌入方式（注意 $G$ 的根不必与 $T$ 的根重合）：

第二个样例的所有十四种可能嵌入方式：