题目描述

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

输入描述

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

输出描述

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

示例1

输入

1 1 3 1 2

输出

3

备注

对于$30 \%$的数据，有$k \leq 10$； 对于$50 \%$的数据，有a=1,b=1； 对于$100 \%$的数据，有$0 \leq k \leq 1000$，$0 \leq n,m \leq k$，且n+m=k，$0 \leq a,b \leq10^6$。