На этот раз наш ребенок раздобыл простой многоугольник. Ему надо найти количество способов разбить многоугольник на невырожденные треугольники таким образом, что:
Ниже приведен рисунок, показывающий пример корректного разбиения.
Пожалуйста, помогите ребенку. Посчитайте описанное количество способов по модулю 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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач