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

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

说明

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

输入格式

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

输出格式

一行一个整数表示答案。

样例

2 3
24

提示

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