CF437E.The Child and Polygon

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:

• 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.

The picture below depicts an example of a correct splitting.

Please, help the child. Calculate the described number of ways modulo 1000000007 (109  +  7) for him.

这一次，我们的孩子得到了一个简单多边形。他需要计算将该多边形划分为若干个非退化三角形的方法数，每种划分方式必须满足以下条件：

• 每个三角形的每个顶点都必须是该多边形的一个顶点；
• 多边形的每条边恰好属于且仅属于一个三角形；
• 任意两个三角形的交集面积为零，且所有三角形的面积之和等于该多边形的面积；
• 每个三角形必须完全位于多边形内部；
• 每个三角形的每条边必须恰好包含多边形的两个顶点。

下图展示了一个正确的划分示例。

请帮助孩子完成这项任务：计算上述方法数，并对 $1000000007$（即 $10^9 + 7$）取模。

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 x__i, y__i (|x__i|, |y__i| ≤ 107) — the i-th vertex of the polygon in clockwise or counterclockwise order.

It's guaranteed that the polygon is simple.

第一行包含一个整数 $n$（$3 \leq n \leq 200$）—— 多边形的顶点数。接下来是 $n$ 行，每行包含两个整数。第 $i$ 行包含 $x_i,\ y_i$（$|x_i|,\ |y_i| \leq 10^7$）—— 按顺时针或逆时针顺序给出的多边形的第 $i$ 个顶点。

保证该多边形是简单多边形。

Output the number of ways modulo 1000000007 (109  +  7).

输出方案数对 1000000007（即 $10^9 + 7$）取模的结果。

In the first sample, there are two possible splittings:

In the second sample, there are only one possible splitting:

在第一个样例中，存在两种可能的划分方式：

在第二个样例中，仅存在一种可能的划分方式：