만드는 중입니다

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

준영이

시간 제한1초메모리 제한1024 MB

요약
N x M 크기의 초콜릿을 직선으로 잘라 조각 넓이의 곱이 최대가 되도록 하고, 그 값을 10^9+7로 나눈 나머지를 구합니다.
난이도

보통10점 중 6점

유형
동적 계획법, 수학
정답자
아직 제출이 없습니다

문제

준영이

준영이는 운동회를 준비하는 친구들에게 나누어 줄 생각으로 가진 초코바를 쪼갠다.

처음에 준영이에게는 가로 길이 NN, 세로 길이 MM인 직사각형 모양의 초코바 조각이 하나 있다. 준영이는 조각 하나를 골라 그보다 작은 조각 2개로 쪼개는 시행을 0회 이상 반복할 수 있다. 시행이 모두 끝난 뒤 모든 조각은 직사각형이어야 하고, 각 변의 길이는 정수여야 한다.

기쁨은 나누면 배가 된다는 속담처럼, 준영이가 얻는 총 기쁨은 시행이 끝난 뒤 남은 조각들의 크기를 모두 곱한 값이다. 가로 길이가 XX이고 세로 길이가 YY인 조각의 크기는 X×YX \times Y로 정의한다.

준영이가 얻을 수 있는 최대 기쁨을 구해보자.

입력

첫째 줄에 정수 NN과 MM이 공백을 사이에 두고 주어진다. (1≤N,M≤1 000)(1 \le N, M \le 1\,000)

출력

준영이가 초코바를 쪼개서 얻을 수 있는 최대 기쁨을 109+710^9+7로 나눈 나머지를 출력한다.

예제3

  1. 예제 1

    입력
    2 2
    
    예상 출력
    4
    
  2. 예제 2

    입력
    1 5
    
    예상 출력
    6
    
  3. 예제 3

    입력
    1000 1000
    
    예상 출력
    206602388