На плоскости отмечены n точек. Точки расположены таким образом, чтобы они образуют правильный многоугольник (отмеченные точки — его вершины, и они пронумерованы по обходу против часовой стрелки). Вам необходимо провести n - 1 отрезков, каждый должен соединять две отмеченные точки, так, чтобы любая точка была достижима из любой другой по некоторому пути из отрезков.
Однако есть некоторые ограничения. Во-первых, некоторые пары точек не могут быть соединены отрезком напрямую. Во-вторых, проведенные отрезки могут касаться только в какой-либо из отмеченных точек (то есть, если на рисунке отрезки пересекаются, и их пересечение не является одной из отмеченных точек, то рисунок некорректный).
Сколько существует способов соединить все вершины, используя n - 1 отрезок? Два способа считаются различными, когда есть такая пара вершин, между которыми есть отрезок в первом способе, но нет во втором. Так как ответ может быть велик, выведите его по модулю 109 + 7.