Inventive and Creative Puppets Corporation (ICPC) 出售各种各样的教育木偶，既面向儿童，也面向那些曾经是儿童且至今仍怀念童年的成年人。为了庆祝其百年华诞，ICPC 决定发售一套其百年历史上最受欢迎的木偶收藏，这无疑会令收藏家们垂涎三尺。

每个木偶的头部都连着一个环，通过这个环，它可以被挂在另一个木偶的两个脚趾中的任意一个下面。每个脚趾最多只能挂一个木偶。由于木偶不喜欢倒立，因此应避免出现木偶环环相扣的闭环。通过将所有木偶挂在另一个木偶的脚趾上，并将最顶端木偶的环挂在墙上，就可以构成一棵木偶树。

你从小就是 ICPC 木偶的忠实粉丝。你喜欢想象木偶的家谱，假设木偶是挂在父辈木偶上的。你还想象了木偶的个性，并决定在形成这棵树时遵守以下规则：

• 每个木偶都有其自身对子节点数量的限制，即最小子节点数和最大子节点数；
• 如果一个木偶有子节点，那么至少有一个子节点的发布日期晚于该木偶。

注意，如果一个木偶有两个子节点，其中一个子节点的发布日期可能早于该木偶。

你想要编写一个程序，计算在满足上述规则的情况下，该收藏集可以构成多少种不同的树。如果任意一个木偶被挂在不同的父节点上，或者被挂在同一个父节点的脚趾上（左脚趾或右脚趾），则认为两棵树是不同的。

输入格式

输入包含单个测试用例，格式如下：

$n$ $x_1$ $y_1$ $\vdots$ $x_n$ $y_n$

第一行包含一个整数 $n$ ($2 \le n \le 300$)，表示木偶的数量。接下来的 $n$ 行中，第 $i$ 行描述了一个木偶的个性。这些行按照木偶的发布日期从旧到新排列。行中的两个整数 $x_i$ 和 $y_i$ 分别是该木偶的最小子节点数和最大子节点数。满足 $0 \le x_i \le y_i \le 2$。

输出格式

输出一行，包含一个整数，表示满足规则的不同树的数量，结果对 $10^9 + 7$ 取模。

样例

样例输入 1

3
0 1
1 2
0 2

样例输出 1

6

样例输入 2

2
0 2
1 2

样例输出 2

0

说明

对于样例 1，有 6 种满足规则的可能树，如图 G.1 所示。

对于样例 2，没有树可以满足规则。

图 G.1. 满足样例 1 规则的树。木偶上的数字代表发布顺序。