该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

具有创造性的木偶公司（$ICPC$）销售各种面向儿童的教育木偶，也为那些曾经是孩子并仍然记得童年的成年人提供服务。为了庆祝百年纪念日，$ICPC$决定推出一系列在其百年历史中最受欢迎的木偶，这无疑将成为收藏家羡慕的对象。

每个木偶的头部都有一个环，可以通过这个环挂在另一个木偶的两个脚趾之一下。每个脚趾最多只能挂一个木偶。由于木偶在倒立位置不舒服，应避免形成木偶循环。因此，可以通过将所有木偶挂在另一个木偶的脚趾上来制作一棵木偶树，最顶部木偶的环可以挂在墙上。

自童年起你就对$ICPC$木偶充满热情。你喜欢想象木偶的家谱，假设木偶挂在父木偶上。你还想象木偶的个性，并决定遵循以下规则来形成树：

1. 每个木偶对子木偶数量有自己的约束，包括最小数量$x_i$和最大数量$y_i$；
2. 如果一个木偶有任何子木偶，至少有一个子木偶的发布日期应晚于父木偶的发布日期。

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

你想编写一个程序来计算满足规则的情况下，可以用这些木偶制作多少种不同的树。如果任何木偶挂在不同的父木偶上，或挂在同一父木偶的不同脚趾上，则认为两棵树是不同的。

输入格式

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

$n$

$x_1$ $y_1$

$\vdots$

$x_n$ $y_n$

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

输出格式

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

数据范围

• $2 \leq n \leq 300$
• $0 \leq x_i \leq y_i \leq 2$

样例数据

3
0 1
1 2
0 2

6

说明

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

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

2
0 2
1 2

0

说明

对于样例输入2，没有树能满足规则。