We are tired and have no ideas for an interesting problem with a backstory. Your task is simply to count convex polygons with short integer sides and no additional lattice points. If we denote the vertices of a polygon as $(x_i, y_i)$, the following conditions must be met:

• $1 \le x_i \le X, 1 \le y_i \le Y$
• The vertices are at lattice points (i.e., $x_i$ and $y_i$ are integers).
• No lattice point lies on any side except for the vertices themselves.
• The length of each side is an integer no greater than $K$.
• The polygon is convex, simple, and non-degenerate (i.e., angles are less than 180 degrees, there are no self-intersections, and there are at least three vertices). This also means that no three vertices are collinear.

Below are examples of invalid polygons. The first and second polygons have a lattice point on one of their sides. The second and third are not convex. Additionally, the first and third have sides whose lengths are not integers.

Output the number of valid polygons modulo $2^{32}$. Two polygons are different if there exists a point that is a vertex of only one of them.

Input

The first and only line of input contains three integers $X, Y$, and $K$ ($1 \le X, Y \le 10^9, 1 \le K \le 250$) – the constraints on the coordinates and the side length, respectively.

The test set is divided into the following subtasks, each worth at least one point. You may assume that every test group belongs to at least one of the subtasks listed below. Note that this implies, for example, that there is no test with $X = Y = K = 233$, as it does not belong to any of the subtasks.

1. $K \le 15$
2. $X, Y \le 150$
3. $2000 \le X, Y \le 2400, K \le 100$
4. $X$ and $Y$ are divisible by $10^6$

Output

Output a single integer – the number of polygons satisfying the problem conditions, modulo $2^{32}$.

Examples

Input 1

6 5 5

Output 1

42

Note

For the example input: $X = 6, Y = 5, K = 5$. One of the 42 valid polygons is the polygon $(2, 1), (2, 2), (6, 5), (3, 1)$, visible in the image.