链接：

来源：牛客网

Chino with Equation

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

Chino的数学很差，因此Cocoa非常担心。今天，Cocoa要教Chino解不定方程。

众所周知，不定方程的解有0个或者若干个。

给出方程:

Cocoa想知道这个不定方程的正整数解和非负整数解各有几个。

题目对Chino来说太难啦，你能帮一帮Chino吗？

输入描述:

两个正整数m, n

输出描述:

题目要求的答案，即正整数解的个数和非负整数解的个数 。由于答案可能会很大，你只需要输出答案 mod(10 9+ 7) 即可。

 

示例1

输入

4 7

输出

20 120 解题思路： 组合数： 1.n,m比较小时：C(n,m)=C(n-1,m)+C(n-1,m-1); 2.卢卡斯定理：n,m比较大时：C(n,m)%mod=C(n%mod,m%mod)*C(n/mod,m/mod)%mod; 第一种情况：将n拆分成m个正整数的和，可以认为将n个小球放入m个盒子，每个盒子都不可为空，可以直接用隔板法，n个小球有n-1的空隙，我们只要在n-1个空隙中选择m-1个空隙放入隔板即可，答案为C(n-1,m-1) 第二种情况：将n拆分成m个非负整数的和，可以认为将n个小球放入m个盒子，但是有的盒子可以为空，不能直接使用隔板法，可以假设我们从外面拿了m个小球，以保证每个盒子至少有一个小球，然后继续又使用隔板法，n+m个小球有n+m-1个间隙，选择其中的m-1个空隙放入隔板就可以了，放完隔板后，每部分取走一个小球即为每个盒子球的个数，方案总数为C(n+m-1,m-1) 直接套用卢卡斯定理模板就可以了 代码：

#include 
           
            #include 
            
             using namespace std;#define ll long long#define mod 1000000007ll n,m,l,r;ll qmul(ll a,ll b){    ll res=0;    while(b){        if(b&1) res=(res+a)%mod;        b>>=1;        a=(a+a)%mod;    }    return res;}ll qpow(ll a,ll b){    ll res=1;    while(b){        if(b&1) res=qmul(res,a);        b>>=1;        a=qmul(a,a);    }    return res;}void exgcd(ll a,ll b,ll &x,ll &y,ll &c){    if(!b){        x=1,y=0,c=a;    }else{        exgcd(b,a%b,y,x,c);        y-=a/b*x;    }}ll INV(ll a,ll p){    ll x,y,c;    exgcd(a,p,x,y,c);    return (x%p+p)%p;}ll C(int a,int b){    if(a
             
              a-b) b=a-b;    ll ca=1,cb=1;    for(int i=0;i