#P10636. BZOJ3518 点组计数

    ID: 12110 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>数论O2优化莫比乌斯反演

BZOJ3518 点组计数

题目描述

平面上摆放着一个 n×mn\times m 的点阵,如下图是一个 3×43\times 4 的点阵图:

现问,有多少个三元点对组 (A,B,C)(A,B,C) 满足 A,B,CA,B,C 三点共线,顺序无关紧要,例如 (A,B,C)(A,B,C)(B,C,A)(B,C,A) 算一组。答案对 109+710^9+7 取模。

输入格式

一行,两个正整数 n,mn,m

输出格式

一行一个整数,表示答案对 109+710^9+7 取模后的结果。

3 4
20

提示

数据保证,1n,m5×1041\leq n,m\leq 5\times 10^4