human
Write me a Python program to find the value of g(n)(x) modulo 109 + 7 given the following:
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
impor
assistant
#Here is Python program to find the value of g(n)(x) modulo 109 + 7.
t 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...