준영이

월간 향유회 2024. 02. -겨울 운동회 편- A번 BOJ 31443번
시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB40619817260.351%

문제

준영이

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

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

기쁨은 나누면 배가 된다는 속담답게, 준영이가 얻는 총 기쁨은 시행이 모두 끝난 뒤 남은 초코바 조각들의 크기의 곱이다. 가로 길이가 $X$이고 세로 길이가 $Y$인 초코바 조각의 크기는 $X \times Y$로 정의한다.

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

입력

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

출력

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

예제 입력 1

2 2

예제 출력 1

4

예제 입력 2

1 5

예제 출력 2

6

$1 \times 2$, $1 \times 3$ 크기로 자르면 기쁨이 $6$이며, 이것보다 기쁨을 크게 만들 수 있는 방법은 없다.

예제 입력 3

1000 1000

예제 출력 3

206602388

출처

Contest > BOJ User Contest > 월간 향유회 > 월간 향유회 2024. 02. -겨울 운동회 편- A번

  • 문제를 만든 사람: pjshwa
  • 문제를 검수한 사람: chogahui05, heeda0528, jyheo98, kiwiyou, lky7674, snrnsidy, utilforever