P14859 [ICPC 2021 Yokohama R] Genealogy of Puppets

**创意与创新木偶公司 (ICPC)** 销售各种教育木偶，面向儿童，也面向那些曾是儿童并依然记得童年时光的成年人。为了庆祝其百年华诞，ICPC 决定发售其百年历史上许多最受欢迎木偶的合集，这无疑将成为收藏家们梦寐以求的珍品。 每个木偶的头部都附有一个环，可以用它将木偶悬挂在另一个木偶的两个脚趾之一下方。一个脚趾最多只能悬挂一个木偶。由于木偶在倒立姿势下会感到不适，应避免形成木偶环。因此，可以通过将所有木偶悬挂在另一个木偶的脚趾上来制作一个木偶 **树**，最顶部的木偶的环则挂在墙上。 你从小就热衷于 ICPC 的木偶。你喜欢想象木偶的家谱，假设木偶被悬挂在一个父木偶上。你还想象木偶的个性，并决定在构建树时遵循以下规则： - 每个木偶对其子木偶数量有自己的限制，即最小值和最大值； - 如果一个木偶有任何子木偶，则其中至少一个子木偶的发售日期应晚于父木偶。 注意，如果一个木偶有两个子木偶，其中一个的发售日期可能早于父木偶。 你想编写一个程序来计算该合集可以制作出多少种 **不同的** 树，且满足上述规则。如果任何木偶悬挂在不同的父木偶上，或悬挂在同一父木偶的不同脚趾上，则认为两棵树是不同的。

输入由单个测试用例组成，格式如下。 $$n$$ $$x_1\ y_1$$ $$\vdots$$ $$x_n\ y_n$$ 第一行包含一个整数 $n$ ($2 \leq n \leq 300$)，表示木偶的数量。接下来的 $n$ 行中，第 $i$ 行描述一个木偶的个性。这些行按木偶的发售日期顺序排列，从较早到较晚。该行中的两个整数 $x_i$ 和 $y_i$ 分别是该木偶子木偶数量的最小值和最大值。满足 $0 \leq x_i \leq y_i \leq 2$。

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

对于样例输入 1，有 6 棵满足规则的树，如图 G.1 所示。 对于样例输入 2，没有树能满足规则。 :::align{center}  图 G.1. 满足样例输入 1 规则的树。木偶上的数字表示发售顺序。 :::