← 返回题目列表

Codeforces · 678/D

D. 迭代线性函数

中文机器翻译题面 查看原题

考虑一个线性函数 f(x) = Ax + B。让我们定义 g(0)(x) = x 和 g(n)(x) = f(g(n - 1)(x)),其中 n > 0。对于给定的整数值 A、B、n 和 x,找到 g(n)(x) 模 109 + 7 的值。

输入

唯一的一行包含四个整数 A、B、n 和 x (1 ≤ A, B, x ≤ 109, 1 ≤ n ≤ 1018) — 问题陈述中的参数。

请注意,给定值 n 可能太大,因此应使用 64 位整数类型来存储它。在 C++ 中,您可以使用 long long 整型,在 Java 中,您可以使用 long 整型。

输出

打印唯一的整数 s — 值 g(n)(x) 模 109 + 7。

示例

输入 #1

3 4 1 1

输出 #1

7

输入 #2

3 4 2 1

输出 #2

25

输入 #3

3 4 3 1

输出 #3

79