我们已经感到疲惫，没有灵感去构思一个带有背景故事的有趣题目。你的任务仅仅是计算满足特定条件的凸多边形的数量，这些多边形具有较短的整数边长，且边上没有额外的格点。
如果我们将多边形的顶点记为 $(x_i, y_i)$，则必须满足以下条件：
- $1 \le x_i \le X, 1 \le y_i \le Y$
- 顶点位于格点上（即 $x_i$ 和 $y_i$ 为整数）。
- 多边形的任何一条边上除了顶点外，不包含其他格点。
- 每条边的长度均为整数，且不超过 $K$。
- 多边形是凸的、简单的、非退化的（即内角均小于 180 度，没有自交，且至少有三个顶点）。这也意味着任意三个顶点都不共线。
下图展示了一些不符合条件的多边形示例。第一个和第二个多边形的某条边上存在格点。第二个和第三个多边形不是凸的。此外，第一个和第三个多边形的某些边长不是整数。
输出满足条件的多边形数量，结果对 $2^{32}$ 取模。如果两个多边形存在一个点是其中一个的顶点但不是另一个的顶点，则认为这两个多边形不同。
输入格式
输入的第一行包含三个整数 $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}$ 取模。
样例
输入 1
6 5 5
输出 1
42
说明 1
对于 $X = 6, Y = 5, K = 5$ 的情况，42 个符合条件的多边形之一是顶点为 $(2, 1), (2, 2), (6, 5), (3, 1)$ 的多边形，如下图所示。