UOJ Logo X Online Judge

XOJ

#5. 神奇的多项式

统计
Time Limit: 1 s Memory Limit: 256 MB

题目描述

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

输入格式

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

输出格式

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

样例数据

input

1 1 3 1 2

output

3

数据规模与约定

对于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。