27948번 - 가지 자르기

유명한 가지 요리사 민규는 오늘도 요리에 사용할 볼록다각형 모양 가지를 손질하고 있다. 민규는 완벽하게 손질된 가지를 만들기 위해 다음 과정에 따라 가지를 자른다.

• 가지를 이루는 각 변의 중점을 이어 새로운 볼록다각형을 만든다. 항상 가지를 자르는 것이 가능함을 보일 수 있다.
• 만들어진 볼록다각형에 포함되지 않는 부분을 잘라 버린다.

왼쪽은 가지를 자르기 전, 오른쪽은 자른 후

민규가 가지를 여러 번 자를수록 가지의 모양은 아름다워지겠지만, 손님들께 낼 가지의 양은 줄어든다.

민규를 위해 가지를 $K$번 자른 후에 가지의 넓이를 구해주자.

첫째 줄에 가지를 이루는 점의 개수 $N$과 가지를 자를 횟수 $K$가 주어진다. $(3\le N\le 1\,000;$ $1\le K\le 10^{18})$

그다음 $N$개의 줄에는 다각형을 이루는 순서대로 $N$개의 점의 좌표 $x$, $y$가 시계방향으로 주어진다. $(0\le x,y\le 10^{9})$

가지를 $K$번 자르고 난 후의 넓이를 유리수 $\frac{P}{Q}$ ($P$와 $Q$는 서로소인 양의 정수)로 표현했을 때, $A\times Q\equiv P$$\pmod{1\,000\,000\,007}$인 정수 $A$ $(0\le A\lt 1\,000\,000\,007)$를 출력한다. 조건을 만족하는 $A$가 유일함을 증명할 수 있다.