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

import sys

def mod_inverse(b,c):
    prod = 1
    while b != 1:
        factor = c/b
        prod = (prod*(factor+1))%c
        b = (factor+1)*b-c
    return prod

def mod_exp(A,n,c):
    max_2 = 1
    A_dict = {0:1,1:A%c,2:(A**2)%c}
    val = (A**2)%c
    power = 2
    while n > power:
        power*=2
        val = (val**2)%c
        A_dict[power] = val
    total = 1
    while n > 0:
        if power <= n:
            n = n - power
            total = (total*A_dict[power])%c
        power = power/2
    return total

def find_value(A,B,n,x):
    A_exp = mod_exp(A,n,10**9+7)
    if A != 1:
        A_less_inv = mod_inverse(A-1,10**9+7)
        A_sum = ((A_exp-1)*(A_less_inv))%(10**9+7)
    else:
        A_sum = n%(10**9+7)
    final_val = (x*A_exp+A_sum*B)%(10**9+7)
    return final_val

if __name__=='__main__':
    ints = sys.stdin.readline().rstrip().split(' ')
    A,B,n,x = int(ints[0]),int(ints[1]),long(ints[2]),int(ints[3])
    print find_value(A,B,n,x)
