[AdditionalFile6464.zip](file://AdditionalFile6464.zip?type=additional_file)

#6464. 「XXOI 2018」劳孙肉饼

标签: 传统 | 时间限制: 50 ms | 内存限制: 5 MiB |

题目描述

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

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

显然劳孙是一个 $N \times M$ 的肉饼（即 $N$ 行 $M$ 列）

XRRRRQAQ 每次可以将一个矩形劳孙啃下来一行或一列（比如是 $1000 \times 6$ 的劳孙，啃下来第 $3$ 列，那就变成了两个劳孙块，分别是 $1000 \times 2$ 和 $1000 \times 3$ 的）

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

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

他想问你：他最多刺激几次呢？？答案对 $1000000007$ 取模

输入格式

一行两个整数 $N,M$。

输出格式

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

样例 1

输入

2 3

输出

5

先啃掉第 $2$ 列，然后就剩下了两个 $2 \times 1$ 的小肉饼，每个都可以啃 $2$ 次（先啃掉一行，再啃掉另一行）

故输出 $1 + 2 \times 2 = 5$

样例 2

输入

3 10

输出

21

样例 3

输入

100 200

输出

10149

数据范围与提示

对于 $30 \%$ 的数据，有 $1 \le N,M \le 3 \times 10^2$；
对于额外 $20 \%$ 的数据，有 $1 \le N \le 4$；
对于额外 $20 \%$ 的数据，有 $1 \le N,M \le 7 \times 10^{14}$；
对于 $100 \%$ 的数据，有 $1 \le N,M \le 10^{18}$。