Consider a linear function *f*(*x*) = *Ax* + *B*. Let's define *g*<sup class="upper-index">(0)</sup>(*x*) = *x* and *g*<sup class="upper-index">(*n*)</sup>(*x*) = *f*(*g*<sup class="upper-index">(*n* - 1)</sup>(*x*)) for *n* &gt; 0. For the given integer values *A*, *B*, *n* and *x* find the value of *g*<sup class="upper-index">(*n*)</sup>(*x*) modulo 10<sup class="upper-index">9</sup> + 7.
The only line contains four integers *A*, *B*, *n* and *x* (1 ≤ *A*, *B*, *x* ≤ 10<sup class="upper-index">9</sup>, 1 ≤ *n* ≤ 10<sup class="upper-index">18</sup>) — 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.
none
3 4 1 1
7
3 4 2 1
25
3 4 3 1
79
1 1 1 1
2
3 10 723 6
443623217
14 81 51 82
908370438
826504481 101791432 76 486624528
621999403
475965351 844435993 96338 972382431
83709654
528774798 650132512 6406119 36569714
505858307
632656975 851906850 1 310973933
230360736
1 1 352875518515340737 1
45212126
978837295 606974665 846646545585165081 745145208
154788991
277677243 142088706 8846851 253942280
221036825
1 192783664 1000000000000000000 596438713
42838179
1 1000000000 1000000000000000000 1
999999665
1 1000000000 1000000000000000000 1000000000
999999657
1 100000000 10000000000000 1000000000
48993
1 1171281 1000000000000000000 100
57392869
1 1000000000 100000000000000000 1000000000
899999965
1 100000000 100000000000000000 10000
490010000
1 100000456 10000000000000000 54165
129054389
1 1000000000 10000000000000 1
490001
1 100000000 10000000000000000 10000
49010000
1 1000000000 10000000000 12
502
1 999999999 999999999999999999 12345678
12345294
1 1000000 1000000000000000000 100000
49100000
1 1000000000 1000000000000 12
49012
1 10000 1000000000000000000 5
490005
1 10000 1000000000000000000 10000
500000
1 1000000000 10000000000000 12
490012
1 1000000000 1000000000000000 12
49000012
1 1000000000 1000000000000000000 12
999999676
1 10000000 100000000000000000 100000
49100000
114514 114514 114514 114514
623380685
2 1 1000000006 1
1
1 1234 10 9
12349
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])


