Junyeong

Time limit1sMemory limit1024 MB

Summary

Given an N by M chocolate bar, split it into rectangles with straight cuts to maximize the product of piece areas, modulo 1e9+7.

Level: Medium6 of 10
Topics: Dynamic programming, Math
Solved: No attempts yet

Problem

Junyeong

Junyeong breaks up the chocolate bars he has so he can share them with friends who are preparing for a sports day.

At the start, Junyeong has one chocolate piece shaped like a rectangle with width $N$ and height $M$ . He may pick one piece and split it into 2 smaller pieces, repeating this 0 or more times. When all splits are finished, every piece must be a rectangle, and each side length must be an integer.

As the proverb says, sharing doubles the joy. The total joy Junyeong gets is the product of the sizes of the remaining pieces after all splits are finished. A piece with width $X$ and height $Y$ has size $X \times Y$ .

Find the maximum joy Junyeong can get.

Input

The first line contains two integers $N$ and $M$ , separated by a space. $(1 \le N, M \le 1\,000)$

Output

Print the maximum joy Junyeong can get from splitting the chocolate, modulo $10^9+7$ .

Examples3

Example 1
Input
```
2 2
```
Expected output
```
4
```
Example 2
Input
```
1 5
```
Expected output
```
6
```
Example 3
Input
```
1000 1000
```
Expected output
```
206602388
```