有一天，Master Zhu 发明了一个有趣的游戏，他将其命名为“树制造者”（Tree Maker）。在这个游戏中，所有的树都是二叉树。

最初，有一棵只有一个顶点的树，且光标位于该顶点上。为了构建这棵树，玩家可以控制光标执行以下五种操作：

• “0”：跳转到当前顶点的父节点（该节点必须存在）。
• “1”：跳转到当前顶点的左孩子（该节点必须存在）。
• “2”：跳转到当前顶点的右孩子（该节点必须存在）。
• “3 $x$”：生成一棵具有 $x$ 个顶点的任意二叉树，并将其作为当前顶点的左子树（执行此操作前，当前顶点必须没有左孩子）。
• “4 $x$”：生成一棵具有 $x$ 个顶点的任意二叉树，并将其作为当前顶点的右子树（执行此操作前，当前顶点必须没有右孩子）。

当执行操作时，日志系统会记录下该操作。

Rin 昨天玩了一整天这个游戏。作为一个健忘的人，尽管 Rin 在玩的时候知道树的形状，但睡了一觉后他忘记了。他现在拥有的只有操作日志。Rin 想知道：根据这份日志，昨天操作结束后，这棵树可能有多少种不同的形状？

你能回答这个问题吗？由于答案可能非常大，你只需要求出其对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $n$，表示日志的行数 ($1 \le n \le 500$)。 接下来 $n$ 行是日志内容。日志格式如上所述。

保证对于每种类型 3 和 4 的操作，整数 $x$ 均为正数，且树中的顶点总数永远不会超过 500。你还可以假设至少存在一棵树使得给定的日志对该树是有效的。

输出格式

输出一行，包含一个整数：Rin 的问题的答案对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

2
3 3
4 3

样例输出 1

25

样例输入 2

2
3 3
1

样例输出 2

5