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.io.OutputStream;
import java.io.PrintWriter;
import java.lang.invoke.LambdaConversionException;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class D {
	
	 long m = (long) (1e9 + 7);
	 
	public void solve(InputReader in, PrintWriter out) {
//       System.out.println(-1mod);
//        System.out.println(m);
		long a, b, n, x;
        a = in.nextLong() % m;
        b = in.nextLong() % m;
        n = in.nextLong() ;
        x = in.nextLong() % m;
        
//        long ax = (a*x) % m;
        long an = pow(a, n);
        
//        if(n!=1) {
	        if(a != 1) {
		        long div = pow(a-1, m-2); // Long.parseLong(new BigInteger(Long.toString(a - 1)).modInverse(new BigInteger("" + m)).toString());
		        
		        long prog = ( ((an - 1+m)%m) *div) % m ;
		        long res = ( ((prog*b)%m) + ((an*x)%m) ) %m;
		        
		        System.out.println(res);
	        } else {
	        	long prog = n % m;
		        long res = ((prog*b)%m + ((an*x)%m) ) %m;
		        
		        System.out.println(res);
	        }
//        } else {
//        	System.out.println( ((a*x)%m + b)%m );
//        }
        
        
//        if(n!=1) {
//	        if(ax != 1) {
//		        long div = Long.parseLong(new BigInteger(Long.toString(ax - 1)).modInverse(new BigInteger("" + m)).toString());
//		        
//		        
//		        long prog = ((axn - 1)*div) % m ;
//		        long res = ((prog*b)%m + axn ) %m;
//		        
//		        System.out.println(res);
//	        } else {
//	        	long prog = n % m;
//		        long res = ((prog*b)%m + axn ) %m;
//		        
//		        System.out.println(res);
//	        }
//        } else {
//        	System.out.println( ((a*x)%m + b)%m );
//        }
		
    }
	
	public long pow(long a, long pow) {
		long res = 1;
		
		while (pow > 0) {
			if(pow%2 == 1) {
				res = (res * a) % m;
			}
			pow /= 2;
			a = (a * a) % m;
		}
		
		return res;
	}
	
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        D solver = new D();
        solver.solve(in, out);
        out.close();
    }

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

        public InputReader(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 nextInt() {
            return Integer.parseInt(next());
        }
        
        public long nextLong() {
            return Long.parseLong(next());
        }
        
        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}
