bzoj#P3260. 跳

题目描述

邪教喜欢在各种各样空间内跳。现在,邪教来到了一个二维平面。在这个平面内,如果邪教当前跳到了 (x,y)(x,y) ,那么他下一步可以选择跳到以下4个点: (x1,y),(x+1,y),(x,y1),(x,y+1)(x-1,y), (x+1,y), (x,y-1), (x,y+1) 。而每当邪教到达一个点,他需要耗费一些体力,假设到达 (x,y)(x,y) 需要耗费的体力用 C(x,y)C(x,y) 表示。

对于 C(x,y)C(x,y) ,有以下几个性质:

  1. x=0x=0 或者 y=0y=0,则 C(x,y)=1C(x,y)=1
  2. x>0x>0y>0y>0,则 C(x,y)=C(x,y1)+C(x1,y)C(x,y)=C(x,y-1)+C(x-1,y)
  3. x<0x<0y<0y<0,则 C(x,y)=C(x,y)= \infty

现在,邪教想知道从 (0,0)(0,0) 出发到 (N,M)(N,M) ,最少花费多少体力(到达 (0,0)(0,0) 点花费的体力也需要被算入)。 由于答案可能很大,只需要输出答案对 109+710^9+7 取模的结果。

输入格式

读入两个整数 N,MN,M ,表示邪教想到达的点。

输出格式

输出仅一个整数,表示邪教需要花费的最小体力对 109+710^9+7 取模的结果。

1 2
6 

提示

对于 100%100\% 的数据,满足 0N,M10120 \le N, M \le 10^12 N×M1012N \times M \le 10^12

题目来源

没有写明来源