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

MOD = 10**9 + 7

def mod(x):
  global MOD
  return x if x < MOD else (x % MOD)


def dot(a, b):
  return mod(sum(map(lambda (x, y): mod(x * y), zip(a, b))))
def eye(n):
  return Matrix([[int(i == j)  for j in range(n)]  for i in range(n)])
def format_row(row, f="%10d"):
  return "[" + " ".join(f % x  for x in row) + "]"


class Matrix:
  def __init__(self, M):
    self.shape = (len(M), len(M[0]))
    self.M = M
    self.T = (
        [[M[j][i]  
            for j in range(self.shape[0])] 
            for i in range(self.shape[1])])
  def copy(self):
    return Matrix(
        [[self.M[i][j]  
            for j in range(self.shape[0])] 
            for i in range(self.shape[1])])
  def dot(self, o):
    return Matrix(
        [[dot(self.M[i], o.T[j])
            for j in range(o.shape[1])]
            for i in range(self.shape[0])])
  def __add__(self, o):
    return Matrix(
        [[mod(self.M[i][j] + o.M[i][j])
            for j in range(o.shape[1])]
            for i in range(o.shape[0])])
  def __str__(self):
    return "[" + "\n ".join(format_row(row) for row in self.M) + "]"
  def pow(self, p):
    answer = eye(self.shape[0])
    B = self.copy()
    while p:
      if p & 1:
        answer = answer.dot(B)
      B = B.dot(B)
      p >>= 1
    return answer

A, B, n, x = map(int, raw_input().split())

A = Matrix([[1, 0], [B, A]])
b = Matrix([[1], [x]])
print A.pow(n).dot(b).M[1][0]

