다각형

우리는 이미 지쳤고 흥미로운 이야기가 있는 문제를 떠올리지 못했다. 그래서 과제는 단순하다. 짧은 정수 변을 가지고 추가 격자점이 없는 볼록 다각형의 개수를 세면 된다. 꼭짓점을 $(x_i, y_i)$라 할 때 다음 조건을 모두 만족해야 한다.

• $1 \le x_i \le X$, $1 \le y_i \le Y$
• 꼭짓점은 격자점이다. 즉 $x_i$와 $y_i$는 정수다.
• 어떤 변 위에도 꼭짓점이 아닌 격자점이 없다.
• 각 변의 길이는 $K$ 이하의 정수다.
• 다각형은 볼록하고 단순하며 퇴화되지 않았다. 모든 내각은 180도보다 작고, 변끼리 교차하지 않으며, 꼭짓점은 최소 세 개다. 또한 세 꼭짓점이 한 직선 위에 있지 않다.

아래 그림은 올바르지 않은 다각형의 예다. 첫 번째와 두 번째 다각형은 변 위에 격자점이 있다. 두 번째와 세 번째 다각형은 볼록하지 않다. 첫 번째와 세 번째 다각형은 변의 길이가 정수가 아니다.

첫 번째이자 유일한 줄에 정수 $X$, $Y$, $K$가 주어진다($1 \le X, Y \le 10^9$, $1 \le K \le 250$). 각각 좌표의 상한과 변 길이의 상한이다.

테스트 데이터는 다음 부분 문제 중 하나 이상에 속한다. 예를 들어 $X = Y = K = 233$인 테스트는 어느 부분 문제에도 속하지 않으므로 존재하지 않는다.

• $K \le 15$
• $X, Y \le 150$
• $2000 \le X, Y \le 2400$, $K \le 100$
• $X$와 $Y$가 $10^6$으로 나누어떨어진다

조건을 만족하는 다각형의 개수를 $2^{32}$로 나눈 나머지를 출력한다. 한쪽 다각형에만 꼭짓점인 점이 있으면 두 다각형은 서로 다른 것으로 본다.

예제 설명이다. $X = 6$, $Y = 5$, $K = 5$이다. 올바른 다각형 42개 중 하나는 꼭짓점이 $(2, 1), (2, 2), (6, 5), (3, 1)$이며, 아래 그림에 나와 있다.