Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

E. Ребенок и многоугольник
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На этот раз наш ребенок раздобыл простой многоугольник. Ему надо найти количество способов разбить многоугольник на невырожденные треугольники таким образом, что:

  • каждая вершина каждого треугольника — это одна из вершин многоугольника;
  • каждая сторона многоугольника должна быть стороной ровно одного треугольника;
  • площадь пересечения любых двух треугольников равна нулю, а сумма всех площадей треугольников равна площади многоугольника;
  • каждый треугольник полностью расположен внутри многоугольника;
  • каждая сторона каждого треугольника должна содержать ровно две вершины многоугольника.

Ниже приведен рисунок, показывающий пример корректного разбиения.

Пожалуйста, помогите ребенку. Посчитайте описанное количество способов по модулю 1000000007 (109  +  7) для него.

Входные данные

В первой строке записано целое число n (3 ≤ n ≤ 200) — количество вершин многоугольника. Затем следует n строк, каждая строка содержит два целых числа: i-я строка содержит xi, yi (|xi|, |yi| ≤ 107)i-ю вершину многоугольника в порядке обхода по или против часовой стрелки.

Гарантируется, что многоугольник простой.

Выходные данные

Выведите количество способов по модулю 1000000007 (109  +  7).

Примеры
Входные данные
4
0 0
0 1
1 1
1 0
Выходные данные
2
Входные данные
4
0 0
1 0
0 1
-1 0
Выходные данные
1
Входные данные
5
0 0
1 0
1 1
0 1
-2 -1
Выходные данные
3
Примечание

В первом примере существует два возможных разделения:

Во втором примере есть только одно возможное разделение: