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

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

输入格式

一行两个整数 n n nm m m

输出格式

一行一个整数表示答案。

样例

样例输入 1

2 3

样例输出 1

24

样例输入 2

10 100

样例输出 2

218427047

样例输入 3

100 1000

样例输出 3

938425419

数据范围与提示

测试点 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