#P3518. 点组计数

    ID: 2729 传统题 1000ms 128MiB 尝试: 195 已通过: 72 难度: 6 上传者: 标签>难度分类提高组合数学贡献法计算几何边界格点 GCD 计数数论欧拉函数构造与建模交换求和顺序线性筛线性代数与代数等差数列求和CF2100

点组计数

点组计数

题目描述

平面上有一个 nn 行、mm 列的等间距矩形点阵,共 nmnm 个点。下图是一个 33 行 44 列的点阵。

三行四列的点阵

Curimit 想知道有多少种方法可以选出三个不同且共线的点。只区分选中了哪些点,三个点的顺序不影响计数。求方案数对 109+710^9+7 取模后的结果。

输入格式

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

输出格式

一行一个整数,表示所求的模值。

样例 #1

3 4
20

数据范围

1≤n,m≤5×1041\le n,m\le 5\times10^4。