4985. 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

10 人解决,38 人已尝试。

11 份提交通过,共有 97 份提交。

7.9 EMB 奖励。

创建: 1 年,10 月前.

修改: 1 年,10 月前.

最后提交: 1 年,8 月前.

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

题目标签