Задача 465: Полярные полигоны
Ядро многоугольника определяется множеством точек, из которых видима граница всего полигона. Мы определяем полярный многоугольник как многоугольник, для которого начало строго содержится внутри его ядра.
Для этой задачи многоугольник может иметь коллинеарные последовательные вершины. Однако многоугольник все еще не может иметь самопересечение и не может иметь нулевую область.
Например, только первое из следующего является полярным многоугольником (ядра второго, третьего и четвертого не содержат строгого начала, а пятый не имеет ядра вообще):
Обратите внимание, что первый многоугольник имеет три последовательные коллинеарные вершины.
Пусть P (n) - число полярных многоугольников, для которых вершины (x, y) имеют целые координаты, абсолютные значения которых не больше n.
Обратите внимание, что многоугольники должны считаться разными, если они имеют различный набор ребер, даже если они заключают одну и ту же область. Например, многоугольник с вершинами [(0,0), (0,3), (1,1), (3,0)] отличается от многоугольника вершинами [(0,0), (0,3) ), (1,1), (3,0), (1,0)].
Например, P (1) = 131, P (2) = 1648531, P (3) = 1099461296175 и P (343) mod 1 000 000 007 = 937293740.
Найти P (713) mod 1 000 000 007.