计树 (tree)

题目描述

统计满足以下条件的 $n$ 个节点的二叉树个数：

1. 第 $i$ 个节点的儿子个数在 $[l_{i}, r_{i}]$ 之间。
2. 如果第 $i$ 个节点不为叶子，且其儿子的最大编号为 $k_{i}$，则需要满足 $k_{i}>i$。

注意左右儿子是区分的。 我们认为两棵树不同，当且仅当在某个点在两棵树中的父亲不同，或是左右儿子不同。

答案对 $10^{9}+7$ 取模。

输入格式

在文件 tree.in 中读入。 本题采用多组测试。 第一行两个非负整数 $tid$ , $T$，其中 $tid$ 表示测试点编号，$T$ 表示数据组数。

对于每组数据： 第一行一个正整数 $n$。 接下来 $n$ 行，每行两个非负整数 $l_{i}$ , $r_{i}$。

输出格式

在文件 tree.out 中输出。 共 $T$ 行，每行一个整数，表示每组数据的答案。

样例

输入数据1

0 3
3
0 2
0 0
0 0
4
0 1
1 2
0 1
0 0
5
0 2
1 1
1 2
0 0
0 2

输出数据1

2
24
88

提示

数据范围与提示

样例 1 解释： 第一组数据： 有两种方案：1为树根，2,3分别为1的左 / 右儿子；2为树根，1,3分别为2的左 / 右儿子。

数据范围

对于所有数据，$1 \le T \le 3$，$1 \le n \le 300$，$0 \le l_{i} \le r_{i} \le 2$。共20个测试点，每个测试点分值相等。

特殊性质 A：$r_{i}<2$ 特殊性质 B：存在且仅存在一个 $i$，满足 $l_{i}=0$