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
import functools
import itertools

class NotAMatrixError(Exception):
    pass

class MatrixSizeError(Exception):
    def __init__(self, s1, s2):
        print('sizes do not match : ', s1, ', ', s2)

class NotSquareError(Exception):
    pass

class Matrix(list):
    def __init__(self, L):
        if type(L) == type(self):
            self = L
            return
        n = len(L)
        m = len(L[0])
        for i in range(n):
            if len(L[i]) != m:
                raise NotAMatrixError()
        list.__init__(self, L)
        self.n = n
        self.m = m
        self.degrees = []
    def check_size(self, M, mode):
        n, m = len(M), len(M[0])
        for i in range(n):
            if len(M[i]) != m:
                raise NotAMatrixError()
        if mode == 'add' and self.n != n or self.m != m:
            raise MatrixSizeError((self.n, self.m), (n,m))
        if mode == 'mul' and self.m != n:
            raise MatrixSizeError((self.n, self.m), (n,m))
    def __add__(self, M):
        self.check_size(M, mode = 'add')
        return Matrix([[self[i][j]+M[i][j] for j in range(self.m)]for i in range(self.n)])
    def __iadd__(self, M):
        self.check_size(M, mode = 'add')
        for i in range(self.n):
            for j in range(self,m):
                self[i][j] += M[i][j]
    def __mul__(self, M):
        self.check_size(M, mode = 'mul')
        l = len(M[0])
        return Matrix([[sum(self[i][k]*M[k][j] for k in range(self.m))
                 for j in range(l)] for i in range(self.n)])
    def issquare(self):
        return self.n == self.m
    def primary(self):
        if self.n != self.m:
            raise NotSquareError()
        return Matrix([[int(i==j) for j in range(self.m)] for i in range(self.n)])
    def __pow__(self, n):
        if self.n != self.m:
            raise NotSquareError()
        if n == 0:
            return self.primary()
        elif n == 1:
            return self
        if len(self.degrees) == 0:
            self.degrees.append(self*self)
        for i in range(n.bit_length() - len(self.degrees) - 1):
            self.degrees.append(self.degrees[-1] * self.degrees[-1])
        s = [(n>>i)&1 for i in range(1,n.bit_length())]
        res = functools.reduce(lambda x,y:x*y, itertools.compress(self.degrees, s))
        return res*self if n%2 else res 
    def drop_degrees(self):
        self.degrees.clear()

class RemMatrix(Matrix):
    def __init__(self, L, p):
        Matrix.__init__(self, L)
        self.p = p

    def primary(self):
        if self.n != self.m:
            raise NotSquareError()
        return Matrix([[Remainder(i==j, self.p) for j in range(self.m)] for i in range(self.n)])

    def __mul__(self, M):
        self.check_size(M, mode = 'mul')
        l = len(M[0])
        return RemMatrix([[sum((self[i][k]*M[k][j] for k in range(self.m)),
                            Remainder(0, self.p)) for j in range(l)]
                       for i in range(self.n)], self.p)

class Remainder(tuple):
    def __new__(self, a, n):
        return tuple.__new__(self, (a%n, n))
    def __add__(self, p):
        return Remainder((self[0] + p[0]) % self[1], self[1])
    def __sub__(self, p):
        return Remainder((self[0] - p[0]) % self[1], self[1])
    def __mul__(self, p):
        return Remainder((self[0] * p[0]) % self[1], self[1])
    def __radd__(self, p):
        return Remainder((self[0] + p[0]) % self[1], self[1])
    def __rsub__(self, p):
        return Remainder((self[0] - p[0]) % self[1], self[1])
    def __rmul__(self, p):
        return Remainder((self[0] * p[0]) % self[1], self[1])
    def __neg__(self):
        return Remainder((-self[0]) % self[1], self[1])

p = 10 ** 9 + 7
r = lambda x : Remainder(x, p)

N = map(r, range(10))

a, b, n, x = map(int, input().split())
a1, b1, o, l, x1 = r(a), r(b), r(0), r(1), r(x)
M = RemMatrix([[a1, b1], [o, l]], p)
L = (M ** n)

print((L[0][0] * x1 + L[0][1])[0])


