题目描述

给定多项式 $(ax + by)^k$ ，需计算该多项式展开后 $x^n y^m$ 项的系数。

输入格式

输入为一行，包含 5 个整数 $a$、$b$、$k$、$n$、$m$ ，整数间用空格分隔。

输出格式

输出一个整数，为所求系数对 $10,007$ 取模后的结果。

数据范围与提示

• 对于 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 \leq 10^6$ 。

样例

输入

1 1 3 1 2

输出

3