평면 위에 정수 좌표를 꼭짓점으로 가지는 단순 다각형이 있다.

다각형의 꼭짓점은 순서대로 주어지며, 서로 인접한 두 꼭짓점은 선분으로 연결된다. 마지막 꼭짓점과 첫 번째 꼭짓점도 연결된다.

이제 정수 \(k\)가 주어질 때마다, 원래 다각형의 모든 꼭짓점 \((x, y)\)를 \((kx, ky)\)로 바꾸어 다각형을 확대한다.

각 질의마다 확대된 다각형의 내부에 있는 격자점의 개수를 구하시오.

단, 답이 매우 클 수 있으므로 \(1\,000\,000\,007\)로 나눈 나머지를 출력한다.

\(3 \le N \le 200\,000\)
\(1 \le Q \le 200\,000\)
\(-10^9 \le x_i, y_i \le 10^9\)
\(1 \le k \le 10^{18}\)
주어지는 다각형은 단순 다각형이다.
꼭짓점은 시계 방향 또는 반시계 방향 순서로 주어진다.

첫째 줄에 다각형의 꼭짓점 개수 \(N\)과 질의 개수 \(Q\)가 주어진다.

둘째 줄부터 \(N\)개의 줄에는 꼭짓점의 좌표 \(x_i, y_i\)가 순서대로 주어진다.

그 다음 줄부터 \(Q\)개의 줄에는 정수 \(k\)가 주어진다.

각 질의마다 확대된 다각형의 내부에 있는 격자점의 개수를 \(1\,000\,000\,007\)로 나눈 나머지를 출력한다.

anthony0506 작성

출처 anthony0506