计算系数

题目描述

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

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

1 1 3 1 2

输出样例 #1

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$。 noip2011提高组day2第1题