题目描述

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

输入格式

一行五个整数 $a$,$b$,$k$,$n$,$m$。

输出格式

一行一个整数，表示系数对 $10007$ 取模的结果。

样例

输入#1

1 1 3 1 2

输出#1

3

数据范围与提示

• 对于 30% 的数据，有 $0 \leq 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$