链接：https://www.nowcoder.com/acm/contest/139/A
来源：牛客网
Count the number of n x m matrices A satisfying the following condition modulo (109+7).
* Ai, j ∈ {0, 1, 2} for all 1 ≤ i ≤ n, 1 ≤ j ≤ m.
* Ai, j ≤ Ai + 1, j for all 1 ≤ i < n, 1 ≤ j ≤ m.
* Ai, j ≤ Ai, j + 1 for all 1 ≤ i ≤ n, 1 ≤ j < m.
* Ai, j ∈ {0, 1, 2} for all 1 ≤ i ≤ n, 1 ≤ j ≤ m.
* Ai, j ≤ Ai + 1, j for all 1 ≤ i < n, 1 ≤ j ≤ m.
* Ai, j ≤ Ai, j + 1 for all 1 ≤ i ≤ n, 1 ≤ j < m.
输入描述:
The input consists of several test cases and is terminated by end-of-file.
Each test case contains two integers n and m.
输出描述:
For each test case, print an integer which denotes the result.
输入例子:
1 2
2 2
1000 1000
输出例子:
6
20
540949876
-->
备注:
* 1 ≤ n, m ≤ 10
3
* The number of test cases does not exceed 10
5
考虑 0101 和 1212 的分界线，用 (n,0)(n,0) 到 (0,m)(0,m) 的两条不相交（可重合）路径，平移其中一条变成 (n−1,−1)(n−1,−1) 到 (−1,m−1)(−1,m−1) 变成起点 (n,0)(n,0) 和 (n−1,−1)(n−1,−1)，终点 (0,m)(0,m) 和 (−1,m−1)(−1,m−1) 的严格不相交路径，套 Lindstrom-Gessel-Viennot lemma 定理。
lgv公式;
#include <iostream>
#include<stdio.h>
#define ll long long
#define mod 1000000007
using namespace std;
ll inv[];
ll jiecheng[];
ll pow (ll a,ll b)
{
ll ans=;
while(b>)
{
if(b%==)
{
ans=ans*a;
ans=ans%mod;
}
b=b/;
a=(a*a)%mod;
}
return ans; }
int main()
{ jiecheng[]=;
for(int i=;i<=;i++)
{
jiecheng[i]=jiecheng[i-]*i;
jiecheng[i]=jiecheng[i]%mod;
}
for(int i=;i<=;i++)
{
inv[i]=pow(jiecheng[i],mod-);
} int n,m;
while(~scanf("%d%d",&n,&m))
{
ll p;
p=(jiecheng[n+m]*inv[n])%mod*inv[m]%mod;
p=p*p%mod;
ll q,w;
q= (jiecheng[n+m]*inv[n+])%mod*inv[m-]%mod;
w=(jiecheng[n+m]*inv[n-])%mod*inv[m+]%mod;
q=q*w%mod; cout<<(p+mod-q)%mod<<endl;
} return ;
}