记录编号	344754	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]计算系数	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.019 s
提交时间	2016-11-10 15:26:19	内存使用	0.33 MiB

#include <cstdio>
#include <cstdlib>
#include <cstdarg>
#include <cstring>
#include <string>
#include <list>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
#define MOD 10007
LL fast_pow(LL base, LL exp)
{
    LL ans = 1;
    base %= MOD;
    while(exp)
    {
        if(exp & 1)
            ans = (ans * base)%MOD;
        exp >>= 1;
        base = (base * base)%MOD;
    }
    return ans;
}
LL xpow[MOD+1];
void pre() //阶乘模MOD意义下的值
{
    xpow[0] = 1;
    for(int i = 1; i <= MOD; i++)
        xpow[i] = (xpow[i-1]*i)%MOD;
}
// lucas(n, k, p) = c(n%p, k%p)*lucas(n/p, k/p, p)
LL lucas(LL n, LL k)
{
    LL ret = 1;
    while(n && k)
    {
        LL a = n%MOD, b = k%MOD;
        if(a < b)return 0;
        ret = ret*xpow[a]*fast_pow(xpow[b]*xpow[a-b]%MOD, MOD-2)%MOD;
        n /= MOD, k /= MOD;
    }
    return ret;
}
int main()
{
    freopen("factor.in", "r", stdin);
    freopen("factor.out", "w", stdout);
    pre();
    LL a, b, k, n, m;
    scanf("%lld %lld %lld %lld %lld", &a, &b, &k, &n, &m);
    LL x = lucas(k, m);
    x = x*fast_pow(a, n)%MOD*fast_pow(b, m)%MOD;
    printf("%lld\n", x);
    return 0;
}