# 3006. 计算多项式的系数 II

$$C_q^r \bmod p \equiv q!{(r!(q - r)!\bmod p)^{p - 2}}\bmod p$$

#include <string>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <queue>

using namespace std;

typedef long long ll;

const ll ceil=1000000007;
ll factors[1000001];

void genlist()
{
for(ll i=0;i<1000001;i++){
if(i==0)
factors[i]=1;
else if(i==1)
factors[i]=1;
else
factors[i]=((factors[i-1]%ceil)*(i%ceil))%ceil;
}
}

ll fastmod(ll a,ll b)
{
ll ret=1;
while(b){
if(b&1)
ret=((ret%ceil)*(a%ceil))%ceil;
a=((a%ceil)*(a%ceil))%ceil;
b>>=1;
}
return ret;
}

ll comp(ll n, ll m)
{
ll res=factors[n]*fastmod((factors[m]*factors[n-m])%ceil,ceil-2)%ceil;
return res;
}

int main()
{
genlist();
int t;
cin>>t;

for(int i=0;i<t;i++){
ll a,b,k,n,m;
cin>>a>>b>>k>>n>>m;

ll comb=comp(k,m);
ll coef_a=fastmod(a,n);
ll coef_b=fastmod(b,m);
ll res=((coef_a%ceil)*(coef_b%ceil))%ceil;
res=((res%ceil)*(comb%ceil))%ceil;

cout<<"case #"<<i<<":"<<endl;
cout<<res<<endl;
}
}


$$\binom{k}{m} = \frac{k!}{m!(k-m)!} = \frac{k!}{m!n!} \equiv k! (m!n!)^{-1} \pmod{p} // p = 1000000007$$

$$a^{p - 1} \equiv 1 \pmod{p} \Rightarrow a \cdot a^{p - 2} \equiv 1 \pmod{p}$$

$$\binom{k}{m} \equiv k!(m!n!)^{-1} \equiv k!(m!n!)^{p - 2} \pmod{p}$$
$$\text{ans} \equiv k!(m!n!)^{p - 2} a^n b^m \pmod{p}$$

nb

#include <iostream>
using namespace std;
using ULLONG = unsigned long long;

constexpr ULLONG P = 1000000007;
constexpr int MAX = 1000001;
ULLONG factorial[MAX];

ULLONG fast_pow(ULLONG _base, ULLONG _pow)
{
ULLONG result = 1;
while (_pow > 0) {
if (_pow & 1)
result = result * _base % P;
_base = _base * _base % P;
_pow >>= 1;
}
return result;
}

void initialize()
{
factorial[0] = 1;
for (int i = 1; i < MAX; ++i)
factorial[i] = factorial[i - 1] * i % P;
}
void solve()
{
int a, b, k, n, m;
cin >> a >> b >> k >> n >> m;
ULLONG inv_binom = fast_pow(factorial[n] * factorial[m] % P, P - 2);
ULLONG apow = fast_pow(a, n);
ULLONG bpow = fast_pow(b, m);

ULLONG ans = factorial[k] * inv_binom % P;
ans = ans * apow % P;
ans = ans * bpow % P;
cout << ans << endl;
}

int main()
{
#ifndef ONLINE_JUDGE
#pragma warning(push)
#pragma warning(disable: 6031)
freopen("D:\\input.txt", "r", stdin);
#pragma warning(pop)
#endif
initialize();
#ifndef SINGLE_CASE
int T;
cin >> T;
cin.get();
for (int t = 0; t < T; ++t) {
cout << "case #" << t << ':' << endl;
solve();
}
#else
solve();
#endif
return 0;
}