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

Input

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.

Output

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

Examples

Input

3 4 1 1

Output

7

Input

3 4 2 1

Output

25

Input

3 4 3 1

Output

79
__aut
=====
Give me a Python program to find the value of g(n)(x) modulo 109 + 7?
assistant
#Here is Python program to find the value of g(n)(x) modulo 109 + 7.
hor__ = 'aste'

MOD = 10**9 + 7

class Matrix:
    def __init__(self, a11, a12, a21, a22):
        self.a11 = a11
        self.a12 = a12
        self.a21 = a21
        self.a22 = a22

    def mul(self, other):
        b11 = self.a11 * other.a11 + self.a12 * other.a21
        b12 = self.a11 * other.a12 + self.a12 * other.a22
        b21 = self.a21 * other.a11 + self.a22 * other.a21
        b22 = self.a21 * other.a12 + self.a22 * other.a22
        b11 %= MOD
        b12 %= MOD
        b21 %= MOD
        b22 %= MOD
        return Matrix(b11, b12, b21, b22)

    def pow(self, n):
        if n == 1:
            return self
        m = self.pow(n//2)
        m = m.mul(m)
        if n % 2 == 1:
            m = m.mul(self)
        return m

def main():
    A, B, n, x = [int(x) for x in input().split()]
    m1 = Matrix(x, 1, 0, 0)
    m2 = Matrix(A, 0, B, 1).pow(n)
    m3 = m1.mul(m2)
    print(m3.a11)

main()