만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

모눈종이와 삼각형

시간 제한2초메모리 제한512 MB

요약
가로 w, 세로 h 격자에서 세 꼬짓점의 넓이가 양의 정수인 순서 있는 삼각형의 개수를 10^9+7로 나눈 나머지를 구한다.
난이도

어려움10점 중 8점

유형
조합론, 수학, 정수론, 기하
정답자
아직 제출이 없습니다

문제

너비가 ww이고 높이가 hh인 모눈종이가 하나 있다. 0≤x≤w0 \le x \le w, 0≤y≤h0 \le y \le h를 만족하는 정수 좌표 (x,y)(x, y)마다 점이 하나씩 찍혀 있으므로, 모눈종이 위의 점은 모두 (w+1)(h+1)(w+1)(h+1)개다.

모눈종이의 점 세 개를 이어서 만들 수 있는 삼각형의 개수를 구하는 프로그램을 작성하시오.

삼각형은 다음 두 조건을 만족해야 한다.

  1. 세 꼭짓점은 모두 정수 좌표를 가져야 한다.
  2. 삼각형의 넓이는 양의 정수여야 한다.

점을 고른 순서가 다르면 다른 삼각형으로 센다. 예를 들어 (0,0)(0, 0), (0,2)(0, 2), (2,2)(2, 2) 순서로 만든 삼각형과 (0,2)(0, 2), (0,0)(0, 0), (2,2)(2, 2) 순서로 만든 삼각형은 서로 다른 삼각형이다.

입력

첫째 줄에 ww와 hh가 공백을 사이에 두고 주어진다. (1≤w,h≤40001 \le w, h \le 4000)

출력

첫째 줄에 조건을 지키면서 만들 수 있는 삼각형의 개수를 109+710^9+7로 나눈 나머지를 출력한다.

예제2

  1. 예제 1

    입력
    2 1
    
    예상 출력
    36
    
  2. 예제 2

    입력
    2 2
    
    예상 출력
    240