You are given a polygon with n sides without self-intersections. In how many ways can you triangulate it?

Input

Input consists of several cases with only integer numbers.
Each case begins with n,
followed by the n coordinates x y of the vertices given in counterclockwise order.
Assume 3 ≤ n ≤ 200
and | x |, | y | ≤ 10^{6}.
The given polygons are such that no triangulation contains a degenerate triangle.

Output

For every case, print the number of triangulations modulo 10^{9} + 7.

Public test cases

**Input**

4 0 0 1 0 1 1 0 1 4 0 0 100000 100000 200000 0 100000 200000 7 2 0 3 2 2 4 0 5 -2 4 -3 2 -2 0 8 1 1 0 3 -1 1 -3 0 -1 -1 0 -3 1 -1 3 0 8 0 0 10 0 10 10 0 10 1 9 9 9 9 1 1 1

**Output**

2 1 42 30 8

Information

- Author
- Gerard Orriols
- Language
- English
- Official solutions
- C++
- User solutions