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

public class Dedu13 {
	static long MOD = 1000000007;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		long A = scan.nextLong(), B = scan.nextLong(), n = scan.nextLong(), x = scan.nextLong();
		long[][] mat = {{A,1L},{0L,1L}};
		long[][] sol = fastExpo(mat, n, MOD);
		System.out.println(((sol[0][0]*x)%MOD+(B*sol[0][1])%MOD)%MOD);
	}
	private static long[][] fastExpo(long[][] A, long n, long m) {
		
		if(n==1)return A;
		
		if(n%2==0){
			long[][] temp = fastExpo(A, n/2, m);
			return matrixMult(temp,temp,m);
		}else{
			long[][] temp = fastExpo(A,n/2,m);
			return matrixMult(A, matrixMult(temp, temp, m), m);
		}
	}
	private static long[][] matrixMult(long[][] A, long[][] B, long m){
		
		long[][] sol = new long[A.length][A.length];
		for(int i=0;i<A.length;i++){
			for(int j=0;j<A.length;j++){
				for(int k=0;k<2;k++){
					sol[i][j]=(sol[i][j]+((A[i][k]*B[k][j])%m))%m;
				}
			}
		}
		return sol;
	}
}
