[NOIP2011 提高组] 计算系数

题目描述

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

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

1 1 3 1 2

输出样例 #1

3

说明

【数据范围】 对于 $30\%$ 的数据,有 $ 0\le k\le 10$。 对于 $50\%$ 的数据,有 $ a=1$,$b=1$。 对于 $100\%$ 的数据,有 $0\le k\le 1000$,$0\le n,m\le k$,$n+m=k$,$0\le a,b\le 10^6$。 noip2011 提高组 day2 第 1 题。