#P13293. [PA2018] Wielokąty
[PA2018] Wielokąty
题目描述
请求出满足以下条件的多边形的个数:
- 记该多边形的第 个顶点为 ,则 且 , 。
- 该多边形的任意一条边(不包含端点)不能经过格点(即横纵坐标都为整数的点)。
- 该多边形的每一条边的长度都是不超过 的整数。
- 该多边形是一个凸多边形,而且不能退化(至少有三个顶点,不自交,所有内角严格小于 ,因此任意三个顶点不共线)。
- 该多边形的每一条边都是线段。
由于满足条件的多边形数量太大,你只需要输出其对 取模后的值即可。
下图展示了三个不合法的多边形。第一个多边形的边经过了格点,第二个多边形退化了,第三个多边形不是凸的。而且第一,三个有的边长不是整数。

两个多边形不同,当且仅当存在一个点只属于其中一个多边形的顶点集合。
输入格式
输入只有一行,包含三个正整数 。
输出格式
输出一行一个整数,即为满足条件的多边形的数量对 取模后的值。
输入输出样例 #1
输入 #1
6 5 5
输出 #1
42
样例解释
四边形 是 个合法多边形中的一个。
可以验证,该多边形满足每一个条件。

数据范围
,。时间限制 秒,内存限制 MB。
原赛每个测试组至少满足以下一项条件。
- 。
- 。
- ,且 。
- 都是 的倍数。