Problem 22743 --多项式系数

22743: 多项式系数

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][92kb]

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

[Submit][Status]