ID: 5061

传统题

1000ms

256MiB

难度: 10

上传者:

标签>

组合数学

计算几何

题目描述

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

输入格式

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

输出格式

一行一个整数表示答案。

样例

样例 1

输入

2 3

输出

样例 2

输入

10 100

输出

218427047

样例 3

输入

100 1000

输出

938425419

数据范围与提示

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