考虑一个线性函数 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