Description

求 (ax+by)^k 的展開中 x^n*y^m 項的系數。由于系數可能很大，只要求輸出除以 10007 的余數。

Input

一行共五個整數，分別為 a,b,k,n,m

Output

一個整數，為該項系數除以10007的余數。

Sample Input

1 1 3 1 2
Sample Output
3
HINT
數據范圍：
30% 0<=k<=10,
50% a=1,b=1
100% 0<=k<=1000, 0<=n,m<=k 且 n+m=k, 0<=a,b<=100,000
NOIP2011 DAY2 factor
Source
NOIP2011
[Submit][Status]
#include<iostream>#include <cmath>#include "cstdio"/* 1、大數一般用10007取模 2、CKN=C(K-1)(N)+C(K-1)(N-1)//排列組合 3、利用以上公式遞歸處理，避免產生大數  */using namespace std;int a,b,k,n,m;int num[1001][1001];int test(int base,int number){    if(num[base][number]!=-1)        return num[base][number];        if(base==number||number==0){        num[base][number]=1;        return num[base][number];    }        num[base][number]=test(base-1,number)+test(base-1,number-1);    num[base][number]%=10007;    return num[base][number];}int main(){               //freopen("/Users/qigelaodadehongxiaodi/Desktop/data1.txt", "r", stdin);    //這個不理，是用來方便輸入輸出的東西，利用文本輸入流來讀取數據    //提交代碼的時候記得注銷這條語句        scanf("%d %d %d %d %d",&a,&b,&k,&n,&m);;        for(int i=0;i<=k;i++)        for(int j=0;j<=k;j++)            num[i][j]=-1;        test(k,n);    num[k][n]%=10007;        for(int i=0;i<n;i++){        num[k][n]*=a%10007;        num[k][n]%=10007;    }        for(int i=0;i<m;i++){        num[k][n]*=b%10007;        num[k][n]%=10007;    }       PRintf("%d/n",num[k][n]%10007);         return 0;}