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
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase
from copy import deepcopy


MOD = 10 ** 9 + 7


transpose = lambda mat: [list(col) for col in zip(*mat)]

minor = lambda mat, i, j: [row[:j] + row[j + 1:] for row in (mat[:i] + mat[i + 1:])]

mat_add = lambda *mat: [[sum(elements) for elements in zip(*row)] for row in zip(*mat)]

mat_sub = lambda A, B: [[i - j for i, j in zip(*row)] for row in zip(A, B)]

mat_mul = lambda A, B: [[sum(i * j for i, j in zip(row, col)) % MOD for col in zip(*B)] for row in A]

vec_mul = lambda mat, vec: [sum(a * b for a, b in zip(row, vec)) % MOD for row in mat]


def eye(m):
    """returns an indentity matrix of order m"""
    identity = [[0] * m for _ in range(m)]
    for i, row in enumerate(identity):
        row[i] = 1
    return identity


def mat_pow(mat, power):
    """returns mat**power"""
    if power < 0:
        return mat_pow(mat_inv(mat), -power)

    result = eye(len(mat))
    if power == 0:
        return result

    while power > 1:
        if power & 1 == 1:
            result = mat_mul(result, mat)
        mat = mat_mul(mat, mat)
        power >>= 1
    return mat_mul(result, mat)


def mat_inv(A):
    B = deepcopy(A)
    n = len(A)
    col = list(range(n))

    tmp = [[0] * n for _ in range(n)]
    for i in range(n):
        tmp[i][i] = 1

    for i in range(n):
        r = c = i
        for j in range(i, n):
            for k in range(i, n):
                if abs(B[j][k]) > abs(B[r][c]):
                    r, c = j, k
        if B[r][c] == 0:
            return B

        B[i], B[r] = B[r], B[i]
        tmp[i], tmp[r] = tmp[r], tmp[i]
        for j in range(n):
            B[j][i], B[j][c] = B[j][c], B[j][i]
            tmp[j][i], tmp[j][c] = tmp[j][c], tmp[j][i]
        col[i], col[c] = col[c], col[i]
        v = B[i][i]
        for j in range(i + 1, n):
            f = B[j][i] / v
            B[j][i] = 0
            for k in range(i + 1, n):
                B[j][k] -= f * B[i][k]
            for k in range(n):
                tmp[j][k] -= f * tmp[i][k]

        for j in range(i + 1, n):
            B[i][j] /= v

        for j in range(n):
            tmp[i][j] /= v
        B[i][i] = 1

    for i in reversed(range(n)):
        for j in range(i):
            v = B[j][i]
            for k in range(n):
                tmp[j][k] -= v * tmp[i][k]

    for i in range(n):
        for j in range(n):
            B[col[i]][col[j]] = tmp[i][j]
    return B


def main():
    A, B, n, x = map(int, input().split())

    mat = [[1, 0], [1, A]]
    vec = [B, x]

    print(vec_mul(mat_pow(mat, n), vec)[1])


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()
