Hide

Problem D
Háhýsi

Languages en is
/problems/hahysi/file/statement/is/img-0001.jpg
Lóðin (mynd fengin af flickr.com)
Siggi sement var nýlega ráðinn sem verktaki til að byggja háhýsi í miðbæ Reykjavíkur. Nýlega fékk hann þær upplýsingar að það er búið að úthluta honum lóð að stærð $n \cdot m$. Siggi er mjög nákvæmur þegar það kemur að starfinu sínu, og langar hann að meta kostnað og fýsileika á öllum mögulegum staðsetningum horna hússins. Kúnninn hans Sigga setti samt enga kröfu um hversu breitt né vítt húsið þarf að vera, svo lengi sem það er að minnsta kosti 1 fermetri og passi inn á lóðina. Lóðinni er skipt upp í reiti sem eru $1$ fermetri hver ($1m \cdot 1m$). Háhýsið þarf að vera rétthyrningur þegar horft er að ofan frá. Hvert einasta horn hússins þarf að vera fyrir miðju í einhverjum reit og engin tvö horn mega vera á sama reit. Siggi hefur ráðið þig í að meta hversu margar mögulegar staðsetningar hann þarf að meta.

Inntak

Fyrsta og eina línan í inntakinu er lengd lóðarinnar, og breidd lóðarinnar, $n$ og $m$, aðskildar með bili. Gefið er að $1 \leq n, m \leq 10^{18}$.

Úttak

Skrifið út fjölda mögulegra staðsetninga á háhýsinu. Þar sem svarið getur verið mjög stórt skaltu skrifa út afganginn á svarinu þegar því er deilt með $10^9 + 7$. Til dæmis ef það eru $1\, 000\, 203\, 876$ mögulegar staðsetningar á hornunum þá skal skrifa út $203\, 869$.

Stigagjöf

Hópur

Stig

Takmarkanir

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