跳
【问题描述】
邪教喜欢在各种各样空间内跳。
现在,邪教来到了一个二维平面。在这个平面内,如果邪教当前跳到了(x,y),
那么他下一步可以选择跳到以下 4 个点:(x-1,y), (x+1,y), (x,y-1), (x,y+1)。
而每当邪教到达一个点,他需要耗费一些体力,假设到达(x,y)需要耗费的体
力用 C(x,y)表示。
对于 C(x,y),有以下几个性质:
1、若 x=0 或者 y=0,则 C(x,y)=1。
2、若 x>0 且 y>0,则 C(x,y)=C(x,y-1)+C(x-1,y)。
3、若 x<0 且 y<0,则 C(x,y)=无穷大。
现在,邪教想知道从(0,0)出发到(N,M),最少花费多少体力(到达(0,0)点花费的体
力也需要被算入)。
由于答案可能很大,只需要输出答案对 10^9+7 取模的结果。
【输入格式】(jump.in)
读入两个整数 N,M,表示邪教想到达的点。
【输出格式】(jump.out)
输出仅一个整数,表示邪教需要花费的最小体力对 10^9+7 取模的结果。
【样例输入】
1 2
【样例输出】
6
【数据说明】
对于 10%的数据,满足 N, M<=20;
对于 30%的数据,满足 N, M<=100;
对于 60%的数据,满足 min(N,M)<=100;
对于 100%的数据,满足 0<=N, M<=10^12,N*M<=10^12。
信息
- 难度
- 9
- 分类
- (无)
- 标签
- (无)
- 递交数
- 14
- 已通过
- 3
- 通过率
- 21%
- 上传者