5617: The Child and Polygon
内存限制：256 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：1
通过：1
题目描述
E. The Child and Polygon
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
This time our child has a simple polygon. He has to find the number of ways to split the polygon into non-degenerate triangles, each way must satisfy the following requirements:
Please, help the child. Calculate the described number of ways modulo 1000000007 (109+7) for him.
- each vertex of each triangle is one of the polygon vertex;
- each side of the polygon must be the side of exactly one triangle;
- the area of intersection of every two triangles equals to zero, and the sum of all areas of triangles equals to the area of the polygon;
- each triangle must be completely inside the polygon;
- each side of each triangle must contain exactly two vertices of the polygon.
Please, help the child. Calculate the described number of ways modulo 1000000007 (109+7) for him.
Input
The first line contains one integer n (3≤n≤200) − the number of vertices of the polygon. Then follow n lines, each line containing two integers. The i-th line contains xi,yi (|xi|,|yi|≤107) − the i-th vertex of the polygon in clockwise or counterclockwise order.
It's guaranteed that the polygon is simple.
Output
Output the number of ways modulo 1000000007 (109+7).
Examples
Input
4 0 0 0 1 1 1 1 0
Output
2
Input
4 0 0 1 0 0 1 -1 0
Output
1
Input
5 0 0 1 0 1 1 0 1 -2 -1
Output
3
Note
In the first sample, there are two possible splittings:
In the second sample, there are only one possible splitting:
输入样例 复制
输出样例 复制