bzoj#P2886. 最短路

最短路

题目描述

小 Y 最近学得了最短路算法,一直想找个机会好好练习一下。话虽这么说,OJ 上最短路的题目都被他刷光了。正巧他的好朋友小 A 正在研究一类奇怪的图,他也想凑上去求下它的最短路。

小 A 研究的图可以这么看:在一个二维平面上有任意整点 (x,y),x[0,n],y[0,m](x,y),x\in[0,n],y\in [0,m],且 (x,y)(x,y)(x1,y)(x-1,y)(必须满足 x1x\ge 1)和 (x,y1)(x,y-1)(必须满足 y1y\ge 1)连一条边权为 00 的双向边。

每个点都有一个非负点权,不妨设 (x,y)(x,y) 的权值为 fx,yf_{x,y},则有:

  1. x=0x=0y=0y=0fx,y=1f_{x,y}=1
  2. 其他情况:fx,y=fx1,y+fx,y1f_{x,y}=f_{x-1,y}+f_{x,y-1}

现在,小 Y 想知道 (0,0)(0,0)(n,m)(n,m) 的最短路,即使得经过的点的权值之和最小。

为了炫耀自己学过最短路算法,他决定和你进行一场比赛,看谁的程序跑得快。然则小 Y 没有学过高精度算法,所以他希望输出答案时只输出答案模 109+710^9+7 后的值。

输入格式

一行两个正整数 n,mn,m

输出格式

一行一个整数表示答案对 109+710^9+7 取模后的值。

1 2
6

数据规模与约定

对于 10%10\% 的数据,1n,m201\leq n,m\leq 20

对于 30%30\% 的数据,1n,m1001\leq n,m\leq 100

对于 60%60\% 的数据,1min{n,m}1001\leq \min\{n,m\}\leq 100

对于 100%100\% 的数据,1n×m10121\leq n\times m\leq 10^{12}