这次我们的孩子有一个简单的多边形。他必须找到将多边形分割成非退化三角形的方法数,每种方法必须满足以下要求:
- 每个三角形的每个顶点都是多边形顶点之一;
- 多边形的每一边必须恰好是一个三角形的边;
- 每两个三角形的交集面积为零,所有三角形面积之和等于多边形面积;
- 每个三角形必须完全位于多边形内部;
- 每个三角形的每条边必须恰好包含多边形的两个顶点。
下图描绘了正确分割的示例。
请帮助孩子。计算他所描述的路数模 1000000007 (109 + 7)。
输入
第一行包含一个整数 n (3 ≤ n ≤ 200) — 多边形的顶点数。然后n行,每行包含两个整数。第 i 行包含 xi, yi (|xi|, |yi| ≤ 107) — 按顺时针或逆时针顺序排列的多边形的第 i 个顶点。
保证多边形是简单的。
输出
输出模 1000000007 (109 + 7) 的路数。
示例
输入 #1
4 0 0 0 1 1 1 1 0
输出 #1
2
输入 #2
4 0 0 1 0 0 1 -1 0
输出 #2
1
输入 #3
5 0 0 1 0 1 1 0 1 -2 -1
输出 #3
3
注意
在第一个示例中,有两种可能的分裂:
在第二个示例中,只有一种可能的拆分: