跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F2708. Little Elephant and Triangle

  • ID: 2714
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:挑战
  • 上传者:
  • 计算几何
  • 数学
  • 挑战
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Little Elephant and Triangle

题目描述

D. Little Elephant and Triangle
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The Little Elephant is playing with the Cartesian coordinates' system. Most of all he likes playing with integer points. The Little Elephant defines an integer point as a pair of integers (x;y), such that 0≤x≤w and 0≤y≤h. Thus, the Little Elephant knows only (w+1)·(h+1) distinct integer points.

The Little Elephant wants to paint a triangle with vertexes at integer points, the triangle's area must be a positive integer. For that, he needs to find the number of groups of three points that form such triangle. At that, the order of points in a group matters, that is, the group of three points (0;0), (0;2), (2;2) isn't equal to the group (0;2), (0;0), (2;2).

Help the Little Elephant to find the number of groups of three integer points that form a nondegenerate triangle with integer area.

Input

A single line contains two integers w and h (1≤w,h≤4000).

Output

In a single output line print an integer − the remainder of dividing the answer to the problem by 1000000007 (109+7).

Examples
Input
2 1
Output
36
Input
2 2
Output
240

题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 2374 题。保留原作者与原赛事署名。