There are n nodes, you should write a program to calculate how many way to form a rooted tree. This tree must satisfy two following conditions:
1: This tree should contain all the n nodes.
2: The size of subtree whose root is node i, should be from $l_i$ to $r_i$.
Give you $l_i$ and $r_i$, you should output the answer.
Input
There are several cases, First is the number of cases T. (There are most ten cases).
For each case, in the first line is a integer n ($1 \leq n \leq 14$). In following n line, each line has two integers $l_i, r_i (1 \leq l_i \leq r_i \leq n$).
Output
For each case output the answer modulo $10^9 + 7$.
Sample Input
2
3
1 3
1 3
1 3
3
1 1
2 2
3 3
Sample Output
9
1
Hint
The first sample: 1 -> 2 -> 3, 1 -> 3 -> 2, 2 <- 1 -> 3, 2 -> 1 -> 3, 2 -> 3 -> 1, 1 <- 2 -> 3,
3 -> 1 -> 2, 3 -> 2 -> 1, 2 <- 3 -> 1(1 -> 2 represent 2¡¯father is 1), these trees satisfy all the conditions.
