CF678D.Iterated Linear Function

Consider a linear function f(x) = Ax + B. Let's define g(0)(x) = x and g(n)(x) = f(g(n - 1)(x)) for n > 0. For the given integer values A, B, n and x find the value of g(n)(x) modulo 109 + 7.

考虑一个线性函数 $f(x) = Ax + B$。定义 $g^{(0)}(x) = x$，且对 $n > 0$，定义 $g^{(n)}(x) = f(g^{(n-1)}(x))$。给定整数 $A$、$B$、$n$ 和 $x$，求 $g^{(n)}(x)$ 对 $10^9 + 7$ 取模的值。

The only line contains four integers A, B, n and x (1 ≤ A, B, x ≤ 109, 1 ≤ n ≤ 1018) — the parameters from the problem statement.

Note that the given value n can be too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.

唯一一行包含四个整数 $A$、$B$、$n$ 和 $x$（$1 ≤ A, B, x ≤ 10^9$，$1 ≤ n ≤ 10^{18}$）——即题目描述中的参数。

注意：给定的值 $n$ 可能非常大，因此你应使用 64 位整数类型来存储它。在 C++ 中可使用 long long 整数类型，在 Java 中可使用 long 整数类型。

Print the only integer s — the value g(n)(x) modulo 109 + 7.

输出唯一的整数 $ s $ —— 即 $ g(n)(x) $ 对 $ 10^9 + 7 $ 取模的值。