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.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Calendar;
import java.util.GregorianCalendar;
import java.util.StringTokenizer;

public class D {

	static final long MOD = 1000000007L;

	static long inv(long x) {
		long b = MOD - 2, r = 1;
		for (; b != 0L; b /= 2) {
			if (b % 2L != 0L)
				r = (r * x) % MOD;
			x = (x * x) % MOD;
		}
		return r;
	}

	public static void main(String[] args) throws IOException {
		File inputFile = new File("entradaD");
		if (inputFile.exists())
			System.setIn(new FileInputStream(inputFile));
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder out = new StringBuilder();
		String line = "";
		while ((line = in.readLine()) != null) {
			long[] v = readLongs(line);
			long a = v[0], b = v[1], n = v[2], x = v[3];
			long modpow = (BigInteger.valueOf(a)).modPow(BigInteger.valueOf(n), BigInteger.valueOf(MOD)).longValue();
			long ans = modpow % MOD;
			ans = (ans * x) % MOD;
			long sum = (modpow - 1) % MOD;
			sum += (sum < 0) ? MOD : 0;
			if (a == 1L)
				sum = n % MOD;
			else {
				long inv = inv(a - 1);
				sum = (sum * inv) % MOD;
			}
			sum = (sum * b) % MOD;
			ans = (ans + sum) % MOD;
			out.append(ans + "\n");
		}
		System.out.print(out);
	}

	static int[] readInts(String line) {
		StringTokenizer st = new StringTokenizer(line.trim());
		int a[] = new int[st.countTokens()], index = 0;
		while (st.hasMoreTokens())
			a[index++] = Integer.parseInt(st.nextToken());
		return a;
	}

	static long[] readLongs(String line) {
		StringTokenizer st = new StringTokenizer(line.trim());
		long a[] = new long[st.countTokens()];
		int index = 0;
		while (st.hasMoreTokens())
			a[index++] = Long.parseLong(st.nextToken());
		return a;
	}

	static double[] readDoubles(String line) {
		StringTokenizer st = new StringTokenizer(line.trim());
		double a[] = new double[st.countTokens()];
		int index = 0;
		while (st.hasMoreTokens())
			a[index++] = Double.parseDouble(st.nextToken());
		return a;
	}
}
