#6464. 萌萌的 RQ

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

题目描述

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

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

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

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

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

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

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

输入格式

一行两个整数 N,MN,M

输出格式

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

样例

样例输入 1

2 3

样例输出 1

5

样例解释 1

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

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

样例输入 2

3 10

样例输出 2

21

样例输入 3

100 200

样例输出 3

10149

数据范围与提示

对于 30%30 \% 的数据,有 1N,M3×1021 \le N,M \le 3 \times 10^2
对于额外 20%20 \% 的数据,有 1N41 \le N \le 4
对于额外 20%20 \% 的数据,有 1N,M7×10141 \le N,M \le 7 \times 10^{14}
对于 100%100 \% 的数据,有 1N,M10181 \le N,M \le 10^{18}