Counting Special Convex Polygons

Given a grid of points with integer coordinates, count the number of distinct convex polygons that satisfy all of the following conditions, and output the result modulo $2^{32}$:

1. The $i$th vertex of the polygon is $(x_i,y_i)$ where $x_i,y_i \in \mathbb{Z}$ and $1 \le x_i \le X$, $1 \le y_i \le Y$.
2. For any edge of the polygon (excluding its endpoints), the edge does not pass through any lattice point (i.e. a point where both coordinates are integers). Equivalently, if an edge connects $(x_1,y_1)$ and $(x_2,y_2)$ then $$\gcd(|x_2-x_1|,|y_2-y_1|)=1.$$
3. The length of every edge is an integer and does not exceed $K$. That is, if an edge from $(x_1,y_1)$ to $(x_2,y_2)$ has length $$\sqrt{(x_2-x_1)^2+(y_2-y_1)^2},$$ then there exists an integer $d$ with $$d=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}\quad \text{and}\quad d\le K.$$
4. The polygon is convex and non-degenerate; in particular, it must have at least three vertices, no three vertices are collinear, it does not self-intersect, and every internal angle is strictly less than $180^\circ$.
5. Two polygons are considered different if they differ in at least one vertex.

The input consists of three integers $X$, $Y$, and $K$. Note that due to the huge number of polygons that can meet the above conditions, you only need to output the total count modulo $2^{32}$.

inputFormat

The input consists of a single line containing three positive integers $X$, $Y$, and $K$, separated by spaces.

outputFormat

Output a single integer: the number of distinct convex polygons satisfying the conditions, taken modulo $2^{32}$.

sample

2 2 3

1