Problem Description

This problem is translated from PA 2018 Round 5 Wielokąty.

You are asked to count the number of polygons that satisfy the following conditions:

• Let the $i$-th vertex of the polygon be $(x_i, y_i)$. Then $x_i, y_i \in \mathbb{Z}$ and $1 \le x_i \le X$, $1 \le y_i \le Y$.
• Any edge of the polygon (excluding its endpoints) must not pass through any lattice point (i.e., a point whose both coordinates are integers).
• The length of every edge of the polygon is an integer not greater than $K$.
• The polygon is convex and must not be degenerate (no three collinear points, no self-intersection, and no angle $\ge 180^{\circ}$).
• Every edge of the polygon is a line segment.

Since the number of such polygons is too large, you only need to output the value modulo $2^{32}$.

The figure below shows three invalid polygons. The first polygon has an edge passing through a lattice point, the second polygon is degenerate, and the third polygon is not convex. Also, in the first and third polygons, some edge lengths are not integers.

We consider two polygons to be different if and only if they have at least one vertex that is different.

Input Format

The input contains only one line with three positive integers $X, Y, K$.

Output Format

Output one integer in one line: the number of polygons that satisfy the conditions modulo $2^{32}$.

6 5 5

42

Hint

Explanation for Sample 1

The figure below shows one of the $42$ valid polygons.

It can be verified that this polygon satisfies every condition.

Constraints

This problem uses bundled testdata.

For $100\%$ of the data, $1 \le X, Y \le 10^9$ and $1 \le K \le 250$.

Translated by ChatGPT 5