题目描述

发明与创造木偶公司（ICPC）为儿童和仍记得童年的成年人销售各种教育木偶。为了庆祝其百年纪念，ICPC 决定出售一套其百年历史中最受欢迎的木偶收藏，这肯定会让收藏家们羡慕不已。

每个木偶的头部都附有一个环，可以将其挂在另一个木偶的两个脚趾之一的下方。每个脚趾上最多只能挂一个木偶。由于木偶不喜欢倒立的姿势，所以应避免形成木偶的循环。通过将所有木偶挂在另一个木偶的脚趾上，并将最上方木偶的环挂在墙上，可以形成一个木偶树。

你从小就对 ICPC 的木偶充满热情。你喜欢想象木偶的族谱，假设木偶挂在父木偶上。你还想象木偶的个性，并决定在构建木偶树时遵守以下规则：

• 每个木偶都有其对子女数量的限制，即最小值和最大值；
• 如果一个木偶有任何子女，至少有一个子女的发行日期晚于父木偶。

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

你想编写一个程序来计算满足上述规则的不同木偶树的数量。如果在任何木偶挂在不同的父木偶上，或者挂在同一父木偶的不同脚趾上，则认为两个木偶树是不同的。

输入

输入由以下格式的一个测试用例组成：

第一行包含一个整数 $n$，满足 $2 \leq n \leq 300$，表示木偶的数量。接下来的 $n$ 行中，第 $i$ 行描述了第 $i$ 个木偶的个性。行按木偶的发行日期从早到晚的顺序排列。每行包含两个整数 $x_i$ 和 $y_i$，分别是该木偶的最小和最大子女数量，且满足 $0 \leq x_i \leq y_i \leq 2$。

输出

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

3
0 1
1 2
0 2

6

2
0 2
1 2

0

样例说明

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

对于样例输入 2，没有任何树可以满足这些规则。