P1313 [NOIP 2011 Senior] Compute the Coefficient

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

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

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

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