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

public class IteratedLinearFunction {

	// https://codeforces.com/contest/678/problem/D
	
	static long mod = (long)1e9 + 7;
	
	public static void main(String[] args) throws IOException, FileNotFoundException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		//BufferedReader in = new BufferedReader(new FileReader("IteratedLinearFunction"));

		StringTokenizer st = new StringTokenizer(in.readLine());
		long a = Long.parseLong(st.nextToken());
		long b = Long.parseLong(st.nextToken());
		long n = Long.parseLong(st.nextToken());
		long x = Long.parseLong(st.nextToken());
		
		long ans = 0;
		if (a!= 1) {
			long aton = pow(a, n);
			ans = aton * x %mod + (b * (aton-1))%mod * modInverse1(a-1, mod)  %mod;
		}
		else {
			ans = x + b*(n%mod)%mod;
		}
		ans = (ans%mod + mod)%mod;
		System.out.println(ans);

	}
	
	public static long pow(long base, long top) {
		long ans  = 1;
		while (top > 0) {
			if (top%2 == 1) {
				ans *= base;
				ans%= mod;
			}
			base*=base;
			base %= mod;
			top >>= 1;
		}
		return ans%mod;
	}
	
	static long c=1,d=1;
	static long modInverse1(long a, long m) {
        long g = gcdExtended(a, m);
        if(g != 1) return -1;
        long res = (c % m + m) % m;
        return res;
    }

    static long gcdExtended(long a, long b) {
        if(a == 0) {
            c = 0;
            d = 1;
            return b;
        }
        long gcd = gcdExtended(b % a, a);
        long x1 = c, y1 = d;
        c = y1 - (b / a) * x1;
        d = x1;
        return gcd;
    }
}
