준영이

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

요약
가로 N, 세로 M인 초코바를 변이 정수인 여러 직사각형으로 잘랐을 때, 모든 조각의 넓이의 곱의 최댓값을 10^9+7로 나눈 나머지를 구한다.
난이도

보통10점 중 5점

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

문제

준영이

준영이는 운동회를 준비하는 친구들을 위해 자신이 가지고 있는 초코바를 쪼갠 뒤 나누어 주려고 한다.

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

기쁨은 나누면 배가 된다는 속담답게, 준영이가 얻는 총 기쁨은 시행이 모두 끝난 뒤 남은 초코바 조각들의 크기의 곱이다. 가로 길이가 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