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

public class Main
{	
	public BufferedReader in;
	public PrintStream out;
	
	public boolean log_enabled = true;
	
	public long M = 1000000007;
	//public long M = 17;
	
	public long A,B;
	
	public long F(long x)
	{
		x =  (A*x + B );
		return   x<M ? x : x % M;
	}
	
	public long pow(long x, long n)
	{
		long r = 1;
		if (n>=M) n = n % (M-1);
		long d = 0x40000000;
		while (d>0)
		{
			r =  r * r % M;
			if ((d & n)>0) r = (r*x) % M;
			d >>= 1;
		}
		
		return r;
	}
	
	public long sumAn(long n)
	{
		if (n==1)
		{
			return 1;
		}
		
		long n2 = n >> 1;
		long x = sumAn(n2);
		
		x = ((x * pow(A, n2)) % M + x) % M;
		
		if ((n & 1) == 1)
		{
			x = (x * A + 1) % M;
		}
		
		return x;
	}
	
	public void test()
	{
		A = readLong();
		B = readLong();
		
		long n = readLong();
		long x = readLong();
		
		/*if (A==1)
		{
			n = n % (M);
			out.println((x + B*n) % M);
			return;
		}*/
		
		long r = pow(A,n) * x % M;
		//logWrite("A^n = %d\n", r);
		long s = sumAn(n);
		//logWrite("sumAn = %d\n", s);
		
		r = ((s * B) % M + r) % M;
		
		out.println(r);
	}
    
	public void run()
	{
		try
		{
			in = new BufferedReader(new InputStreamReader(System.in));
			out = System.out;
			
			//in = new BufferedReader(new FileReader("in.txt"));
			//out = new PrintStream(new File("out.txt"));
			
			
		}
		catch (Exception e)
		{
			return;
		}
		
		//while (true)
		{
			//int t = readInt(); for (int i=0; i<t; i++)					
			{
				test();
			}
		}
	}
	
	public static void main(String args[])
	{
		new Main().run();
	}
	
	private StringTokenizer tokenizer = null;
	
	public int readInt() 
	{
        return Integer.parseInt(readToken());
    }
   
    public long readLong() 
	{
        return Long.parseLong(readToken());
    }
   
    public double readDouble() 
	{
        return Double.parseDouble(readToken());
    }
   
	public String readLn()
	{	
		try
		{
			String s;
			while ((s = in.readLine()).length()==0);
			return s;
		}
		catch (Exception e)
		{
			return "";
		}
	}
	
    public String readToken() 
	{
		try
		{
			while (tokenizer == null || !tokenizer.hasMoreTokens()) 
			{
				tokenizer = new StringTokenizer(in.readLine());
			}
			return tokenizer.nextToken();
		}
		catch (Exception e)
		{
			return "";
		}
    }
	
	public int[] readIntArray(int n)
	{
		int[] x = new int[n];
		readIntArray(x, n);
		return x;
	}
	
	public void readIntArray(int[] x, int n)
	{
		for (int i=0; i<n; i++)
		{
			x[i] = readInt();
		}
	}
	
	public void logWrite(String format, Object... args)
	{
		if (!log_enabled)
		{
			return;
		}
		
		out.printf(format, args);
	}
}

