多边形内部能够完整观察到多边形边界上所有点的点集称为其多边形的核。核的内部包含原点的多边形被称为极点多边形。

本问题中的多边形可以有相邻的共线顶点，但其边界不会自相交，面积也不会为零。

例如，下图的多边形中只有第一个是极点多边形（第二、三个多边形的核中不含原点，第四个多边形的核包含原点，但原点在边界上，第五个多边形没有核）：

此外，可以注意到第一个多边形中有三个相邻的共线顶点。

记$P(n)$是满足各顶点的坐标均为整数且绝对值不大于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) \bmod 1000000007=937293740$。

求$P(7^{13}) \bmod 10^9+7$。

本题难度:

解答

记O为原点，把范围内所有的点分割成若干个等价类，原点单独一类，其它情况当且仅当A, B, O共线时A,B在同一个等价类中。亦即同一等价类中的点的极角或者相同或者相差一个负号。

那么极点多边形的顶点在不同的等价类中且不集中在一个半平面上，按此要求递推计算即得结果$585965659$。

注：因使用cache装饰器作记忆化搜索，以下代码为Python 3。

import math
from functools import *

n=7**13
mod=10**9+7

@cache
def coprime_pair(n):
    #a=round(math.sqrt(n))+1
    a=math.isqrt(n)+1
    res=4*n*n+4*n-sum(coprime_pair(n//i) for i in range(2,a))
    k=n//a
    while k:
        b=n//k+1
        res-=coprime_pair(k)*(b-a)
        a,k=b,k-1
    return res

a=math.isqrt(n)+1
x1,x2,x3=1,0,0
for i in range(1,a):
    cnt=coprime_pair(n//i)-coprime_pair(n//(i+1))>>1
    x1=x1*pow(i+1,cnt%(mod-1),mod)%mod
    x2=(x2+cnt*i*2)%mod
    x3=(x3+cnt*i*i)%mod
k=n//a
while k:
    b=n//k+1
    cnt=coprime_pair(k)-coprime_pair(k-1)>>1
    x1=x1*pow(b,cnt%(mod-1),mod)%mod
    x2=(x2+cnt*(b-1)*2)%mod
    x3=(x3+cnt*(b-1)*(b-1))%mod
    a,k=b,k-1

print((x1*(x1-x2)-1+x3)%mod)