#P18818. [Croatian CPC2016] Ograda

[Croatian CPC2016] Ograda

[Croatian CPC2016] Ograda

题目描述

在标准平面直角坐标系中,xx 轴向右,yy 轴向上。

对于每个左下角坐标为非负整数 (x,y)(x,y)、边平行于坐标轴的单位正方形,定义其价值为 x!y!x!y!。其中,0!=10!=1,对 t≥1t\ge1,t!=1×2×⋯×tt!=1\times2\times\cdots\times t。

现在用一条各边均平行于坐标轴的多边形围栏围住一片区域。请计算围栏内部所有单位正方形的价值之和,对 109+710^9+7 取模。

输入格式

第一行包含一个正整数 nn(n≤100n\le100),表示多边形的顶点数。

接下来 nn 行,第 kk 行包含两个整数 xk,ykx_k,y_k(0≤xk,yk≤1090\le x_k,y_k\le10^9),按沿边界的顺序给出第 kk 个顶点。最后一个顶点与第一个顶点也相连。

保证这些顶点构成一个简单多边形,各边平行于坐标轴,且相邻的两条边从不平行。顶点可能按顺时针或逆时针顺序给出。

输出格式

输出一个整数,表示所求价值之和对 109+710^9+7 取模的结果。

样例 1

输入

4
1 1
1 2
2 2
2 1

输出

1

样例 2

输入

4
3 3
1 3
1 1
3 1

输出

9

样例 3

输入

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

输出

119

样例说明

下图展示了样例 3 的围栏及各个单位正方形的价值。

样例3示意图