CF1288C-Two Arrays （DP）
You are given two integers n and m. Calculate the number of pairs of arrays (a,b) such that:
the length of both arrays is equal to m; each element of each array is an integer between 1 and n (inclusive); ai≤bi for any index i from 1 to m; array a is sorted in non-descending order; array b is sorted in non-ascending order. As the result can be very large, you should print it modulo 109+7.
Input The only line contains two integers n and m (1≤n≤1000, 1≤m≤10).
Output Print one integer – the number of arrays a and b satisfying the conditions described above modulo 109+7.
Examples Input 2 2 Output 5 Input 10 1 Output 55 Input 723 9 Output 157557417 Note In the first test there are 5 suitable arrays:
a=[1,1],b=[2,2]; a=[1,2],b=[2,2]; a=[2,2],b=[2,2]; a=[1,1],b=[2,1]; a=[1,1],b=[1,1].
#include <bits/stdc++.h>
using namespace std;
template <typename t>
void read(t &x)
{
char ch = getchar();
x = 0;
t f = 1;
while (ch < '0' || ch > '9')
f = (ch == '-' ? -1 : f), ch = getchar();
while (ch >= '0' && ch <= '9')
x = x * 10 + ch - '0', ch = getchar();
x *= f;
}
#define wi(n) printf("%d ", n)
#define wl(n) printf("%lld ", n)
#define rep(m, n, i) for (int i = m; i < n; ++i)
#define rrep(m, n, i) for (int i = m; i > n; --i)
#define P puts(" ")
typedef long long ll;
#define MOD 1000000007
#define mp(a, b) make_pair(a, b)
#define N 10005
#define fil(a, n) rep(0, n, i) read(a[i])
//---------------https://lunatic.blog.csdn.net/-------------------//
ll dp[1000][100];
int main()
{
int n,m;
read(n),read(m);
m*=2;;
for(int i=1;i<=n;i++)
dp[1][i]=1;
for(int i=2;i<=m;i++)
for(int j=n;j>0;j--)
dp[i][j]=(dp[i][j+1]+dp[i-1][j])%MOD;
ll ans=0;
for(int i=1;i<=n;i++)
ans=(ans+dp[m][i])%MOD;
cout<<ans<<endl;
return 0;
} 腾讯云开发者
