Fence

Time limit3sMemory limit512 MB

Summary

Sum x! times y! over all unit cells inside an axis-aligned polygon, modulo 1e9+7, with coordinates up to 1e9.

Level: Hard8 of 10
Topics: Math, Prefix sum, Geometry, Number theory
Solved: No attempts yet

Problem

A pasture where factorials grow lies in the standard coordinate system, where the $x$ coordinate increases to the right and the $y$ coordinate increases upward. A cell is a square with side length 1 and sides parallel to the coordinate axes, such that both coordinates of its lower left corner $A = (x_A, y_A)$ are nonnegative integers. The value of such a cell is $x_A! \times y_A!$ , where $a! = 1 \times 2 \times \cdots \times a$ for $a \ge 1$ and $0! = 1$ .

A fence is a polygon whose sides are parallel to the coordinate axes. Given a fence, compute the sum of the values of all cells inside the fence, modulo $10^9 + 7$ .

Input

The first line contains a positive integer $n$ ( $n \le 100$ ), the number of vertices of the fence.

The $k$ -th of the next $n$ lines contains integers $x_k$ and $y_k$ ( $0 \le x_k, y_k \le 10^9$ ), the coordinates of the $k$ -th vertex of the fence. The vertices are listed in order along the polygon.

You may assume that the vertices form a polygon whose sides are parallel to the coordinate axes. In particular, the polygon does not intersect itself, and two adjacent sides are never parallel.

Output

Print the requested sum modulo $10^9 + 7$ on the first line.

Hint

The figure shows the fence from the third example and the value of each cell. The values of the cells inside the fence add up to 119.

Examples3

Example 1
Input
```
4
1 1
1 2
2 2
2 1
```
Expected output
```
1
```
Example 2
Input
```
4
3 3
1 3
1 1
3 1
```
Expected output
```
9
```

Example 3

Input

Expected output