题目描述

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

输入格式

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

输出格式

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

样例

输入

1 1 3 1 2

输出

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$。