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

public class Edu13_D {
	static final long MOD = 1_000_000_007;
	public static long pow(long base, long pow) {
		if(pow == 0)
			return 1;
		long res = pow%2==0?1:base;
		long base2 = pow(base, pow/2);
		return ((res%MOD*base2%MOD)%MOD*base2)%MOD;
	}
	public static void main(String[] args) throws IOException {
		BufferedInputStream bis = new BufferedInputStream(System.in);
		BufferedReader br = new BufferedReader(new InputStreamReader(bis));
		PrintWriter out = new PrintWriter(System.out);
		String line;
		StringTokenizer st;
		while ((line = br.readLine()) != null && !line.equals("")) {
			st = new StringTokenizer(line);
			long ans, A = Long.parseLong(st.nextToken());
			long B = Long.parseLong(st.nextToken());
			long n = Long.parseLong(st.nextToken());
			long x = Long.parseLong(st.nextToken());
			if(A == 1)
				ans = (x+B*(n%MOD))%MOD;
			else {
				long r = pow(A, n);
				long r2 = pow(A-1, MOD-2);
				long t = ((r-1)*r2)%MOD;
				ans = (r*x+t*B)%MOD;
			}
			out.println(ans);
		}
		out.close();
	}
}