Grid paper and triangles

Time limit2sMemory limit512 MB

Summary

Count ordered triples of lattice points in a (w+1) by (h+1) grid whose triangle has positive integer area, modulo 1e9+7.

Level: Hard8 of 10
Topics: Combinatorics, Math, Number theory, Geometry
Solved: No attempts yet

Problem

A sheet of grid paper is $w$ wide and $h$ tall. Every integer coordinate $(x, y)$ with $0 \le x \le w$ and $0 \le y \le h$ carries a dot, so the sheet holds $(w+1)(h+1)$ dots.

Write a program that counts the triangles you can build by joining three dots of the grid paper.

A triangle must satisfy both conditions below.

All three vertices have integer coordinates.
The area of the triangle is a positive integer.

Triangles built from the same dots in a different order count as different triangles. For example, the triangle built from $(0, 0)$ , $(0, 2)$ , $(2, 2)$ and the triangle built from $(0, 2)$ , $(0, 0)$ , $(2, 2)$ are two different triangles.

Input

The first line contains $w$ and $h$ , separated by a space ( $1 \le w, h \le 4000$ ).

Output

Print the number of triangles that satisfy the conditions, modulo $10^9+7$ , on the first line.

Examples2

Example 1
Input
```
2 1
```
Expected output
```
36
```
Example 2
Input
```
2 2
```
Expected output
```
240
```