#6464. 萌萌的RQ

内存限制:5 MiB 时间限制:50 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: KingSann

题目描述

XRRRRQAQ 去学文化的的样子太萌啦!!!

XRRRRQAQ 在课上太无聊,以至于吃起了劳孙(你不用知道这是什么)

显然劳孙是一个 N×MN \times MN×M 的肉饼(即 NNNMMM 列)

XRRRRQAQ 每次可以将一个矩形劳孙啃下来一行或一列(比如是 1000×61000 \times 61000×6 的劳孙,啃下来第 333 列,那就变成了两个劳孙块,分别是 1000×21000 \times 21000×21000×31000 \times 31000×3 的)

XRRRRQAQ 每吃一次劳孙都可能引起劳师的注意,这很刺激

XRRRRQAQ 为了寻求最多的刺激,打算用最多的次数吃完这个大劳孙

他想问你:他最多刺激几次呢??答案对 100000000710000000071000000007 取模

输入格式

一行两个整数 N,MN,MN,M

输出格式

一行一个整数,表示答案。

样例

样例输入 1

2 3

样例输出 1

5

样例解释 1

先啃掉第 222 列,然后就剩下了两个 2×12 \times 12×1 的小肉饼,每个都可以啃 222 次(先啃掉一行,再啃掉另一行)

故输出 1+2×2=51 + 2 \times 2 = 51+2×2=5

样例输入 2

3 10

样例输出 2

21

样例输入 3

100 200

样例输出 3

10149

数据范围与提示

对于 30%30 \%30% 的数据,有 1≤N,M≤3×1021 \le N,M \le 3 \times 10^21N,M3×102
对于额外 20%20 \%20% 的数据,有 1≤N≤41 \le N \le 41N4
对于额外 20%20 \%20% 的数据,有 1≤N,M≤7×10141 \le N,M \le 7 \times 10^{14}1N,M7×1014
对于 100%100 \%100% 的数据,有 1≤N,M≤10181 \le N,M \le 10^{18}1N,M1018