Description

Given a polynomial $(by+ax)^k$, compute the coefficient of the term $x^n\times y^m$ in its expansion.

Input Format

The input contains one line with $5$ integers, namely $a, b, k, n, m$, separated by a single space.

Output Format

Output one line containing a single integer, which is the required coefficient. This coefficient may be large; output the result modulo $10007$.

1 1 3 1 2

3

Hint

Constraints

• For $30\%$ of the testdata, $0\le k\le 10$.
• For $50\%$ of the testdata, $a=1$, $b=1$.
• For $100\%$ of the testdata, $0\le k\le 1000$, $0\le n, m\le k$, $n + m = k$, $0\le a, b\le 10^6$.

NOIP 2011 Senior Day 2 Problem 1.

Translated by ChatGPT 5