Problem 465
Polar polygons
The kernel of a polygon is defined by the set of points from which the entire polygon’s boundary is visible. We define a polar polygon as a polygon for which the origin is strictly contained inside its kernel.
For this problem, a polygon can have collinear consecutive vertices. However, a polygon still cannot have self-intersection and cannot have zero area.
For example, only the first of the following is a polar polygon (the kernels of the second, third, and fourth do not strictly contain the origin, and the fifth does not have a kernel at all):
Notice that the first polygon has three consecutive collinear vertices.
Let P(n) be the number of polar polygons such that the vertices (x, y) have integer coordinates whose absolute values are not greater than n.
Note that polygons should be counted as different if they have different set of edges, even if they enclose the same area. For example, the polygon with vertices [(0,0),(0,3),(1,1),(3,0)] is distinct from the polygon with vertices [(0,0),(0,3),(1,1),(3,0),(1,0)].
For example, P(1) = 131, P(2) = 1648531, P(3) = 1099461296175 and P(343) mod 1 000 000 007 = 937293740.
Find P(713) mod 1 000 000 007.
极点多边形
多边形的核心指的是多边形内能够观察到多边形的所有边界的点集。如果一个多边形的核心严格包含原点，这个多边形被称为极点多边形。
在这个问题中，一个多边形允许包含连续的共线顶点，但是多边形不允许自交，面积也不能为零。
例如，以下的图形中只有第一个是极点多边形（第二、三、四个多边形的核心不严格包含原点，第五个多边形没有核心）：
可以注意到第一个多边形中有三个连续的共线顶点。
记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。