题目详情 - #6050. 「雅礼集训 2017 Day11」TRI - 图灵编程OJ

ID: 350

传统题

1000ms

256MiB

难度: (无)

上传者:

说明

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

</div> </div>

输入格式

一行两个整数 $n$ 和 $m$ 。

输出格式

一行一个整数表示答案。

样例

样例输入 1

2 3

样例输出 1

样例输入 2

10 100

样例输出 2

218427047

样例输入 3

100 1000

样例输出 3

938425419

数据范围与提示

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