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,math
def power(x, y, p): 
    res = 1;
    x = x % p;  
    while (y > 0):   
        if (y & 1): 
            res = (res * x) % p; 
        y = y >> 1;  
        x = (x * x) % p; 
    return res; 
def modInverse(b,m): 
	g = math.gcd(b, m) 
	if (g != 1):  
		return -1
	else:  
		return pow(b, m - 2, m)  
def modDivide(a,b,m): 
	a = a % m 
	inv = modInverse(b,m) 
	if(inv == -1): 
		print("Division not defined") 
	else: 
		return (inv*a) % m    
#using sum of GP series 
A,B,n,X=map(int,sys.stdin.readline().split())
m=10**9+7
if A==1:
    print(((n%m)*B+X)%m)
else:
    temp=power(A,n,m)
    s=(temp*(X%m))%m
    s=(s%m+((modDivide(B*(temp-1),A-1,m)%m)%m)%m)%m
    print(s%m)
