Rose is no longer satisfied by math, so she lets Jack start to learn geometry.

Today they work on such a problem: Given a simple polygon of n vertices on a plane, how many different triangulations of this polygon are there? The answer needs to module .

: A polygon that does not intersect itself and has no holes.

: An edge set contains diagonal lines, and these lines only intersect at polygon vertices. These lines separate a simple polygon into triangles.

The first line contains one integer  () --- the number of vertices.

The next  lines contain the coordinates of the polygon vertices, where the -th line contains two integers ,  () --- the coordinates of the polygon's -th vertex. The vertices are given clockwise or counterclockwise.

It is guaranteed that no three vertices are collinear.

Output one integer in one line --- the number of different triangulations module .

6
0 10
2 6
5 3
4 1
10 0
0 0

3