Xiao z has a graph with $n$ nodes, where the nodes are numbered from $0$ to $n-1$.

There is an edge between every pair of nodes in the graph. The weight of the edge connecting nodes $i$ and $j$ ($i < j$) can be any integer in the range $[l_{i,j}, r_{i,j}]$.

For a graph where all edge weights are fixed, its value is defined as the product of the weights of all edges in its minimum spanning tree.

Xiao z wants to know the sum of the values of all possible graphs.

You only need to output the answer modulo $1034567892$ (a non-prime number).

Input

The first line contains an integer $n$ ($2 \le n \le 8$). The following $\frac{n(n-1)}{2}$ lines provide the intervals for the edges $(i, j)$ in order of increasing $i$ as the first key and increasing $j$ as the second key ($1 \le i < j \le n$). Each line contains two integers, representing $l_{i,j}$ and $r_{i,j}$ respectively, satisfying $1 \le l_{i,j} \le r_{i,j} \le 10^9$.

Output

Output a single integer representing the answer.

Examples

Input 1

2
1 10

Output 1

55

Input 2

3
1 7
2 8
3 9

Output 2

5663

Input 3

4
1 10
1 10
1 10
1 10
1 10
1 10

Output 3

47751154

Input 4

3
1 2
1 2
1 2

Output 4

14