题目描述
小 Y 最近学得了最短路算法,一直想找个机会好好练习一下。话虽这么说,OJ 上最短路的题目都被他刷光了。正巧他的好朋友小 A 正在研究一类奇怪的图,他也想凑上去求下它的最短路。
小 A 研究的图可以这么看:在一个二维平面上有任意整点 (x,y),x∈[0,n],y∈[0,m],且 (x,y) 向 (x−1,y)(必须满足 x≥1)和 (x,y−1)(必须满足 y≥1)连一条边权为 0 的双向边。
每个点都有一个非负点权,不妨设 (x,y) 的权值为 fx,y,则有:
- 当 x=0 或 y=0:fx,y=1;
- 其他情况:fx,y=fx−1,y+fx,y−1。
现在,小 Y 想知道 (0,0) 到 (n,m) 的最短路,即使得经过的点的权值之和最小。
为了炫耀自己学过最短路算法,他决定和你进行一场比赛,看谁的程序跑得快。然则小 Y 没有学过高精度算法,所以他希望输出答案时只输出答案模 109+7 后的值。
输入格式
一行两个正整数 n,m。
输出格式
一行一个整数表示答案对 109+7 取模后的值。
1 2
6
数据规模与约定
对于 10% 的数据,1≤n,m≤20;
对于 30% 的数据,1≤n,m≤100;
对于 60% 的数据,1≤min{n,m}≤100;
对于 100% 的数据,1≤n×m≤1012。