NOI
全国青少年信息学奥林匹克联赛(NOIPOJ)在线评测系统
NOIPOJ在线评测系统
Problem16--计算系数

16: 计算系数

Time Limit: 1000 Sec  Memory Limit: 128 MB
Submit: 7  Solved: 2
[Submit] [Status] [Web Board] [Creator:]

Description

给定一个多项式(by+ax)^k,请求出多项式展开后x^n*y^m 项的系数。

Input

输入文件名为factor.in。

共一行,包含5 个整数,分别为 a ,b ,k ,n ,m,每两个整数之间用一个空格隔开。

Output

输出共1 行,包含一个整数,表示所求的系数,这个系数可能很大,输出对10007 取模后的结果

Sample Input Copy

1 1 3 1 2

Sample Output Copy

3

HINT

【数据范围】

对于30% 的数据,有 0 ≤k ≤10 ;

对于50% 的数据,有 a = 1,b = 1;

对于100%的数据,有 0 ≤k ≤1,000,0≤n, m ≤k ,且n + m = k ,0 ≤a ,b ≤1,000,000。

Source/Category