Bracket Sequence ——卡特兰数

平衡括号序列是一个仅由括号"("和")"组成的字符串。
一天，卡罗尔问贝拉长度为2N（N对括号）的平衡括号序列的数量。作为心算大师，她立刻算出了答案。所以Carol问了一个更难的问题：长度为2N（N对括号）、括号类型为K的平衡括号序列的数量。贝拉不能马上回答，请帮帮她。
形式上，你可以用K种类型的括号定义平衡括号序列，其中：ε（空字符串）是平衡括号序列；如果A是平衡括号序列，那么lAr也是，其中l表示左括号，r表示右括号。lr必须彼此匹配并且形成K种类型的括号中的一种。如果A和B是平衡括号序列，那么AB也是。
例如，如果我们有两种类型的括号"()"和"[]"，"()[]"、"[()]"和"([])"是平衡括号序列，而"[(])"和"([)]"不是。因为"(]"和"[)"不能形成，不能相互匹配。

输入：
一行包含两个整数N和K：表示对的数量和类型的数量。保证1≤K，N≤105。

输出：
一行包含一个整数：长度为2N（N对括号）、具有K种括号类型的平衡括号序列的数量。因为答案可能太大，所以以109+7为模输出。

样例输入1：
1 2
样例输出1：
2

样例输入2：
2 2
样例输出2：
8

样例输入3：
24 20
样例输出3：
35996330

解析：

所以本题可以直接套公式。注意除法取模等同于乘以分母的乘法逆元取模！！！

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pair<int,int> PII;
const int N=2e6+10,p=1e9+7;
int qmi(int a,int k)
{
    int ans=1;
    while (k)
    {
        if (k&1) ans=ans*a%p;
        k >>=1;
        a=a*a%p;
    }
    return ans;
}
int C(int a,int b)
{
    int ans=1;
    for (int i=1,j=a;i<=b;i++,j--)
    {
        ans=ans*j%p;
        ans=ans*qmi(i,p-2)%p;
    }
    return ans;
}
int lucas(int a,int b)
{
    if (a<p&&b<p) return C(a,b);
    return C(a%p,b%p)*lucas(a/p,b/p)%p;
}
int n,k;
signed main()
{
    ios;
    cin>>n>>k;
    int ans=lucas(n+n,n)%p;
    ans=ans*qmi(n+1,p-2)%p;   //不能直接除以(n+1),没有除法取模！！
    ans=ans*qmi(k,n)%p;      
    cout<<ans;
    return 0;
}