该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

【题意】
某城市的街道呈网格状，左下角坐标为 A(0, 0)，右上角坐标为 B(n, m)，其中 $n \ge m$。现在从 A(0, 0) 点出发，只能沿着街道向正右方或者正上方行走，且不能经过图示中直线左上方的点，即任何途径的点 (x, y) 都要满足$ x \ge y$，请问在这些前提下，到达 B(n, m) 有多少种走法。
;

【输入格式】
仅有一行，包含两个整数 n 和 m，表示城市街区的规模（$1\le m\le n\le 5000$）。

【输出格式】
仅有一个整数和一个换行/回车符，表示不同的方案总数。

【样例输入】
6 6

【样例输出】
132

Hint

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e4+10;
const LL P=1e9;
int n, m, pr, prime[N]; bool v[N]; 
void init()
{
	pr=0; memset(v, 0, sizeof(v));
	for(int i=2; i<=n+m; i++) 
	{
		if(v[i]==0) prime[++pr]=i;
		for(int j=1; j<=pr && (i*prime[j]<=n+m); j++)
		{
			v[i*prime[j]]=1;
			if(i%prime[j]==0) break;
		}
	}
}
struct node
{
	int len; LL a[2100];
	node() {len=1; memset(a, 0, sizeof(a));}
};
node operator+(node n1, node n2)
{
	node no; no.len=max(n1.len, n2.len);
	for(int i=1; i<=no.len; i++) no.a[i]=n1.a[i]+n2.a[i];
	for(int i=1; i<=no.len; i++)
	{
		no.a[i+1]+=no.a[i]/P;
		no.a[i]%=P; 
	}
	int i=no.len;
	while(no.a[i+1]>0)
	{
		i++;
		no.a[i+1]+=no.a[i]/P;
		no.a[i]%=P; 
	}
	while(i>1 && no.a[i]==0) i--;
	no.len=i;
	return no;
}
node operator-(node n1, node n2)
{
	node no; no.len=max(n1.len, n2.len);
	for(int i=1; i<=no.len; i++) no.a[i]=n1.a[i]-n2.a[i];
	for(int i=1; i<=no.len; i++) if(no.a[i]<0)
	{
		no.a[i]+=P; no.a[i+1]--;
	}
	int i=no.len;
	while(i>1 && no.a[i]==0) i--;
	no.len=i;
	return no;
}
node operator*(node n1, LL x)
{
	node no; no.len=n1.len;
	for(int i=1; i<=no.len; i++) no.a[i]=n1.a[i]*x;
	for(int i=1; i<=no.len; i++)
	{
		no.a[i+1]+=no.a[i]/P;
		no.a[i]%=P; 
	}
	int i=no.len;
	while(no.a[i+1]>0)
	{
		i++;
		no.a[i+1]+=no.a[i]/P;
		no.a[i]%=P; 
	}
	while(i>1 && no.a[i]==0) i--;
	no.len=i;
	return no;
}
node C(int n, int m)
{
	node ans; ans.a[1]=1; int M, cnt;
	for(int i=1; i<=pr; i++)
	{
		if(prime[i]>n) break;
		M=n; cnt=0;
		while(M>0) M/=prime[i], cnt+=M;
		M=m;
		while(M>0) M/=prime[i], cnt-=M;
		M=n-m;
		while(M>0) M/=prime[i], cnt-=M;
		while(cnt--) ans=ans*prime[i];
	}
	return ans;
}
void putnum(LL x)
{
	LL t=P/10;
	while(x<t) printf("0"), t/=10;
	printf("%d", x);
}
int main()
{
	scanf("%d%d", &n, &m); init();
	node ans=C(n+m, m)-C(n+m, m-1);
	printf("%lld", ans.a[ans.len]);
	for(int i=ans.len-1; i>=1; i--) putnum(ans.a[i]);
	printf("\n");
	return 0;
}