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.
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$).
For each case output the answer modulo $10^9 + 7$.