#P2886. 最短路

    ID: 1993 传统题 1000ms 512MiB 尝试: 110 已通过: 58 难度: 7 上传者: 标签>CF2200提高势能分析组合数乘法递推逆元线性递推对称性分析

最短路

题目描述

小 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) 向 (x−1,y)(x-1,y)(必须满足 x≥1x\ge 1)和 (x,y−1)(x,y-1)(必须满足 y≥1y\ge 1)连一条边权为 00 的双向边。

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

  1. 当 x=0x=0 或 y=0y=0:fx,y=1f_{x,y}=1;
  2. 其他情况:fx,y=fx−1,y+fx,y−1f_{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\% 的数据,1≤n,m≤201\leq n,m\leq 20;

对于 30%30\% 的数据,1≤n,m≤1001\leq n,m\leq 100;

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

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