Educational Codeforces Round 80 C. Two Arrays（组合数快速取模）

You are given two integers nn and mm . Calculate the number of pairs of arrays (a,b)(a,b) such that:

the length of both arrays is equal to mm ;
each element of each array is an integer between 11 and nn (inclusive);
ai≤biai≤bi for any index ii from 11 to mm ;
array aa is sorted in non-descending order;
array bb is sorted in non-ascending order.

As the result can be very large, you should print it modulo 109+7109+7 .

Input

The only line contains two integers nn and mm (1≤n≤10001≤n≤1000 , 1≤m≤101≤m≤10 ).

Output

Print one integer – the number of arrays aa and bb satisfying the conditions described above modulo 109+7109+7 .

Examples

Input

2 2

Output

Input

10 1

Output

Input

723 9

Output

157557417

由题意可知，这个题所求的两个序列实际上可以合并成一个，将递增序列的头部接到递减序列的尾部，所得一个长为2m的序列。原问题可以转化为求范围1到n的2m个数组成的递增序列的个数（一个序列里可以有两个重复的数）。官方题解直接用Python+组合数公式

from math import factorial as fact

mod = 10**9 + 7

def C(n, k):

    return fact(n) // (fact(k) * fact(n - k))

n, m = map(int, input().split())

print(C(n + 2*m - 1, 2*m) % mod)

从原理入手，当这2m个数里有i个数不相同时，先从n个位置里用C(n,i)算出当前有几种选法，接下来有2m-i个数是和刚刚选出来的序列的部分数相同，可以看作同球入不同盒问题直接应用公式计算即可，每次循环更新ans。题目要求取模，这里借鉴了https://www.csdn.net/gather_2b/NtzaIgxsNzQtYmxvZwO0O0OO0O0O.html里组合数快速取模的知识。

#include <bits/stdc++.h>

#define MOD 1000000007

using namespace std;

long long n,m;

int inv(int a)

{

    return a==?:(long long)(MOD-MOD/a)*inv(MOD%a)%MOD;

}

long long C(long long n,long long m)//组合数快速取模

{

    if(m<)return ;

    if(n<m)return ;

    if(m>n-m)m=n-m;

    long long up=,down=;

    long long i;

    for(i=;i<m;i++)

    {

        up=up*(n-i)%MOD;

        down=down*(i+)%MOD;

    }

    return up*inv(down)%MOD;

}

int main()

{

    cin>>n>>m;

    int i;

    long long ans=;

    for(i=*m;i>=;i--)//有i个不同的数

    {

        if(i>n)continue;

        ans=(ans+C(n,i)*/*同球入不同盒 2*m-i入i */ C(*m-i+i-,i-))%MOD;

    }

    printf("%lld",ans);

    return ;

}

巴特西

Educational Codeforces Round 80 C. Two Arrays（组合数快速取模）

最新文章

热门文章