题目描述

题目译自 PA 2018 Runda 5 Wielokąty 。

请求出满足以下条件的多边形的个数：

• 记该多边形的第 $i$ 个顶点为$(x_i,y_i)$ ，则 $x_i,y_i \in \mathbb{Z}$ 且 $1 \le x_i \le X$ , $1 \le y_i \le Y$ 。
• 该多边形的任意一条边（不包含端点）不能经过格点（即横纵坐标都为整数的点）。
• 该多边形的每一条边的长度都是不超过 $K$ 的整数。
• 该多边形是一个凸多边形，而且不能退化（不能出现三点共线，自切，不小于 $180 ^{\circ}$ 的角）。
• 该多边形的每一条边都是线段。

由于满足条件的多边形数量太大，你只需要输出其对 $2^{32}$ 取模后的值即可。

下图展示了三个不合法的多边形。第一个多边形的边经过了格点，第二个多边形退化了，第三个多边形不是凸的。而且第一，三个有的边长不是整数。

我们将两个多边形看做不相同的多边形，当且仅当它们有至少一个顶点不相同。

输入格式

输入只有一行，包含三个正整数 $X,Y,K$ 。

输出格式

输出一行一个整数，即为满足条件的多边形的数量对 $2^{32}$ 取模后的值。

6 5 5

42

数据范围与提示

对于任何一个测试点，有 $1 \le X,Y \le 10^9,1 \le K \le 250$ 。

有 $4$ 个子任务，每个子任务至少包含一个测试点。每一个测试点至少归属于 $4$ 个子任务之一。

比如，不可能出现一个测试点，其中 $X=Y=K=233$ 。因为包含该数据的测试点不属于任何一个子任务。

1. $K \le 15$
2. $X,Y \le 150$
3. $2000 \le X,Y \le 2400,K \le 100$
4. $X,Y \equiv 0 \pmod {10^6}$