题目描述

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

输入格式

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

输出格式

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

样例

样例输入

1 1 3 1 2

样例输出

3

提示

对于$\red{30\%}$ 的数据，有 $\red{k\leq 10}$；

对于$\red{50\%}$ 的数据，有 $\red{a = 1，b = 1}$；

对于$\red{100\%}$ 的数据，有 $\red{0\leq k\leq 1,000}$，$\red{0\leq n, m\leq k}$，且 $\red{n + m = k}$，$\red{0\leq a，b\leq 1,000,000}$ 。