Number of triangulations P45584


Statement
 

pdf   zip

thehtml

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 | ≤ 106. The given polygons are such that no triangulation contains a degenerate triangle.

Output

For every case, print the number of triangulations modulo 109 + 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
    C++