单点时限: 2.0 sec
内存限制: 256 MB
Even if the guidance has been broken, please calculate the Golden Formula:
$$\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor}x^{n-k\times i}y^iC_{n-(k-1)\times i}^{i}$$
The answer may be very large, so please output the answer modulo $10^9+7$.
The only line contains $4$ integers $x,y,n,k$ $(1\leq x,y,n\leq 10^9,1\leq k\leq 100)$.
Output one integer indicating the answer modulo $10^9+7$.
1 2 3 4
1
11 4 51 4
896238515