Hide

Problem K
Háhýsi

/problems/iceland.hahysi/file/statement/en/img-0001.jpg
The site (image from flickr.com)
Siggi cement was recently hired to build skyscrapers in downtown Reykjavík. He recently received the info that he has been assigned a site of size $n \cdot m$. Siggi is very precise when it comes to his job and wants to estimate the cost and feasibility of all possible locations for the corners of the building. Siggi’s customer put no constraints on how wide the building has to be in either direction, as long as it’s at least one square meter and fits the site. The site is divided into squares, each being $1$ square meter ($1m \cdot 1m$). The skyscraper has to be a rectangle when viewed from above. Each corner has to be in the center of some square and no two corners may be in the same square. Siggi has assigned you the task of finding how many possible locations he has to look into.

Input

The first and only line of the input is the length and width of the site, $n$ and $m$, separated by a space. It is guaranteed that $1 \leq n, m \leq 10^{18}$.

Output

Print the number of possible locations for the skyscraper. Since the answer could be very large you should print the remainder of the answer when it is divided by $10^9 + 7$. For example if there are $1\, 000\, 203\, 876$ possible locations, you should print $203\, 869$.

Scoring

Group

Points

Scoring

1

10

$1 \leq n, m \leq 7$

2

10

$1 \leq n, m \leq 50$

3

20

$1 \leq n, m \leq 200$

4

20

$1 \leq n, m \leq 2\, 000$

5

20

$1 \leq n, m \leq 10^6$

6

20

$1 \leq n, m \leq 10^{18}$

Sample Input 1 Sample Output 1
2 2
1
Sample Input 2 Sample Output 2
3 4
18

Please log in to submit a solution to this problem

Log in