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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class A
{


	static long MOD = 1000*1000*1000L + 7;
	public static long[][] matrixAdd(long[][] a, long[][] b) {
		int n = a.length;
		int m = a[0].length;
		long[][] res = new long[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				res[i][j] = a[i][j] + b[i][j];
			}
		}
		return res;
	}

	public static long[][] matrixMul(long[][] a, long[][] b) {
		int n = a.length;
		int m = a[0].length;
		int k = b[0].length;
		long[][] res = new long[n][k];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < k; j++) {
				for (int p = 0; p < m; p++) {
					res[i][j] = ((res[i][j]%MOD) + (a[i][p]%MOD) * (b[p][j]%MOD))%MOD;
				}
			}
		}
		return res;
	}

	public static long[][] matrixPow(long[][] a, long p) {
		if (p == 0) {
			return matrixUnit(a.length);
		} else if (p % 2 == 0) {
			return matrixPow(matrixMul(a, a), p / 2);
		} else {
			return matrixMul(a, matrixPow(a, p - 1));
		}
	}

	public static long[][] matrixPowSum(long[][] a, long p) {
		int n = a.length;
		if (p == 0) {
			return new long[n][n];
		}
		if (p % 2 == 0) {
			return matrixMul(matrixPowSum(a, p / 2), matrixAdd(matrixUnit(n), matrixPow(a, p / 2)));
		} else {
			return matrixAdd(a, matrixMul(matrixPowSum(a, p - 1), a));
		}
	}

	public static long[][] matrixUnit(int n) {
		long[][] res = new long[n][n];
		for (int i = 0; i < n; ++i) {
			res[i][i] = 1;
		}
		return res;
	}


	public static void main(String[] args)
	{


		IR in = new IR(System.in);
		long a = in.ll(); long b = in.ll(); long n = in.ll(); long x = in.ll();

		long initial[][] = { {1L,a*x+b}, {0,0} };
		long trans[][] =   { {1L,b} ,{0,a} };
		

		long res[][] = matrixMul(initial,matrixPow(trans,n - 1));

		System.out.println(res[0][1]);


	}

	static	class IR {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public IR(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int j() {
			return Integer.parseInt(next());
		}
		public long ll(){
			return Long.parseLong(next());
		}

	}
}