2023 年上海市大学生程序设计竞赛 - 一月赛

E. Golden Formula

单点时限: 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$.

样例

Input
1 2 3 4
Output
1
Input
11 4 51 4
Output
896238515