Problem1709--计算系数

1709: 计算系数

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 5  Solved: 5
[Submit] [Status] [Web Board] [Creator:]

Description

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

Input

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

Output

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

Sample Input Copy

1 1 3 1 2

Sample Output Copy

3

HINT

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

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

对于 100% 的数据,有 0 ≤ k ≤ 1000≤ n,m ≤ k,且 n+m=k ,≤ a,b≤ 10^6

Source/Category

 入门