#P3260. 跳

跳

跳

题目描述

你从整数格点 (0,0)(0,0) 出发,每步可以向上、下、左、右移动一个单位。 所有移动均须在第一象限及坐标轴上进行,即始终满足 x,y≥0x,y\ge0。

到达格点 (x,y)(x,y) 时消耗体力 C(x,y)C(x,y),定义为:

  • 若 x=0x=0 或 y=0y=0,则 C(x,y)=1C(x,y)=1。
  • 若 x,y>0x,y>0,则 C(x,y)=C(x−1,y)+C(x,y−1)C(x,y)=C(x-1,y)+C(x,y-1)。

起点的体力消耗也计入。求到达 (N,M)(N,M) 的最少体力消耗,并将结果对 109+710^9+7 取模。 最少消耗先在普通整数意义下确定,再取模。

输入格式

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

输出格式

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

样例

1 2
6

数据范围

0≤N,M≤10120\le N,M\le10^{12},NM≤1012NM\le10^{12}。