Polygons

We are already tired and have no idea for an interesting story problem. The task is simply to count convex polygons with short integer sides and no extra lattice points. Let the vertices be $(x_i, y_i)$. The following conditions must hold.

• $1 \le x_i \le X$, $1 \le y_i \le Y$
• The vertices are lattice points, so $x_i$ and $y_i$ are integers.
• No lattice point lies on any side except the vertices themselves.
• The length of each side is an integer not greater than $K$.
• The polygon is convex, simple, and non-degenerate. Every interior angle is less than 180 degrees, no edges cross, and there are at least three vertices. No three vertices are collinear.

The figure below shows invalid polygons. The first and second have a lattice point on one of their sides. The second and third are not convex. The first and third have sides whose lengths are not integers.

The first and only line contains three integers $X$, $Y$, and $K$ ($1 \le X, Y \le 10^9$, $1 \le K \le 250$). They are the bounds on the coordinates and on the side length.

Each test group belongs to at least one of the following subtasks. For example, there is no test with $X = Y = K = 233$, because it fits no subtask.

• $K \le 15$
• $X, Y \le 150$
• $2000 \le X, Y \le 2400$, $K \le 100$
• $X$ and $Y$ are divisible by $10^6$

Print the number of valid polygons modulo $2^{32}$. Two polygons are different if some point is a vertex of one of them but not the other.

In the sample, $X = 6$, $Y = 5$, $K = 5$. One of the 42 valid polygons has vertices $(2, 1), (2, 2), (6, 5), (3, 1)$, shown in the figure below.