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 java.math.BigInteger;
import java.util.Scanner;

public class IteratedLinearFunction {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
		long b = sc.nextLong();
		long n = sc.nextLong();
		long x = sc.nextLong();
		
		long m = 1000000007;
		if (a==1){
			System.out.println((new BigInteger(x+"").add(new BigInteger(n+"").multiply(new BigInteger(b+""))).mod(new BigInteger(m+""))).toString());
			return;
		}
		
		BigInteger an = po(a,n,new BigInteger(""+m));
		BigInteger an1 = po(a,n,new BigInteger(""+m).multiply(new BigInteger((a-1)+"")));
		an1 = ((an1.add(new BigInteger(""+m).multiply(new BigInteger((a-1)+""))).subtract(new BigInteger("1"))).divide(new BigInteger((a-1)+"")).mod(new BigInteger(""+m)));
		System.out.println((an.multiply(new BigInteger(x+"")).mod(new BigInteger(m+"")).add(an1.multiply(new BigInteger(b+""))).mod(new BigInteger(m+""))));
	}

	private static BigInteger po(long a, long n, BigInteger m) {
		if (n==0) return new BigInteger("1");
		if (n==1) return new BigInteger(""+a);
		BigInteger r1 = po(a,n/2,m);
		BigInteger r2 = po(a,n%2,m);
		BigInteger br1 = new BigInteger(r1+"");
		BigInteger br2 = br1.multiply(br1);
		BigInteger brmod = br2.mod(new BigInteger(m+""));
		brmod = brmod.multiply(new BigInteger(r2+""));
		brmod = brmod.mod(new BigInteger(m+""));
		return brmod;
	}

}
