#781. #6050. 「雅礼集训 2017 Day11」TRI

#6050. 「雅礼集训 2017 Day11」TRI

题目描述

给定 nn 和 mm,求出所有顶点坐标满足 0≤x<n,0≤y<m0 \leq x \lt n, 0 \leq y \lt m 的格点三角形的面积和的两倍。答案模 10045358091004535809 输出。

输入格式

一行两个整数 nn 和 mm。

输出格式

一行一个整数表示答案。

2 3
24
10 100
218427047
100 1000
938425419

数据范围与提示

测试点 nn mm
1 ≤10\leq 10
2 ≤20\leq 20
3 ≤30\leq 30
4 ≤40\leq 40
5 ≤50\leq 50
6 ≤60\leq 60
7 ≤100\leq 100
8 ≤200\leq 200
9 ≤300\leq 300
10 ≤400\leq 400
11 ≤1000\leq 1000
12 ≤2000\leq 2000
13 ≤2500\leq 2500
14 ≤3000\leq 3000
15 ≤1000\leq 1000 ≤109\leq 10 ^ 9
16 ≤1500\leq 1500
17 ≤2000\leq 2000
18 ≤2500\leq 2500
19 ≤2800\leq 2800
20 ≤3000\leq 3000