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
#!/usr/bin/python
import sys
import re

def input_numbers():
    return [int(n) for n in raw_input().split()]

A,B,n,x = input_numbers()
MOD = 10 ** 9 + 7

def mul(m1, m2):
    a,b,c,d = m1[0][0], m1[0][1], m1[1][0], m1[1][1]
    x,y,z,w = m2[0][0], m2[0][1], m2[1][0], m2[1][1]
    return (((a*x + b*z) % MOD, (a*y + b*w) % MOD), ((c*x + d*z) % MOD, (c*y + d*w) % MOD))

def square(m):
    return mul(m, m)

def power(m, n):
    if n == 0:
        return ((1, 0), (0, 1)) #Id
    sq = power(square(m), n / 2)
    if n % 2 == 1:
        sq = mul(m, sq)
    return sq

m = ((A, 0), (B, 1))
mn = power(m, n)

A,B = mn[0][0], mn[1][0]
print (A*x + B) % MOD

