【NOIP2011提高组】计算系数

#include<bits/stdc++.h>
using namespace std;
int f1=1,f2=1,a,b,k,n,m,ans,yh[1005]= {0,1},yh2[1005]= {0,1};
void yanghui(int x)
{
    if(x%2==0)
        for(int i=2; i<=x+1; i++)
            yh2[i]=(yh[i-1]+yh[i])%10007;
    else if(x%2==1)
        for(int i=2; i<=x+1; i++)
            yh[i]=(yh2[i-1]+yh2[i])%10007;
    if(x+1!=k)
        yanghui(x+1);
}
int fang()
{
    for(int i=1; i<=n; i++)
        f1=(f1*a)%10007;
    for(int i=1; i<=m; i++)
        f2=(f2*b)%10007;
    return (f1*f2)%10007;
}
int main()
{
    //freopen("factor.in","r",stdin);
    //freopen("factor.out","w",stdout);
    scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
    a=a%10007,b=b%10007;
    if(k==0||k==1)
    {
        cout<<0;
        return 0;
    }
    k++;
    yanghui(1);
    k--;
    if(k%2==1)ans=(fang()*yh[n+1])%10007;
    if(k%2==0)ans=(fang()*yh2[k-n+1])%10007;
    printf("%d",ans);
}