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.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class ECR13D {
	static final BigInteger MOD=BigInteger.valueOf(1_000_000_007);
	public static void main(String[] args) {
		FastScanner in=new FastScanner();
		BigInteger a=BigInteger.valueOf(in.nextLong());
		BigInteger b=BigInteger.valueOf(in.nextLong());
		BigInteger n=BigInteger.valueOf(in.nextLong());
		BigInteger x=BigInteger.valueOf(in.nextLong());
		
		if(a.equals(BigInteger.ONE))
			System.out.println(x.add(n.mod(MOD).multiply(b)).mod(MOD));
		else{
			BigInteger p=POW(a,n);
			BigInteger q=POW(a.subtract(BigInteger.ONE),MOD.subtract(BigInteger.valueOf(2)));
			BigInteger ans=p.multiply(x).mod(MOD).add(p.subtract(BigInteger.ONE).multiply(b).mod(MOD).multiply(q).mod(MOD)).mod(MOD);
			System.out.println(ans.longValue());
		}
	}
	static final BigInteger POW(BigInteger a,BigInteger n){
		if(a.equals(BigInteger.ONE)) return BigInteger.ONE;
		if(n.equals(BigInteger.ZERO)) return BigInteger.ONE;
		if(n.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) return POW(a.multiply(a).mod(MOD),n.divide(BigInteger.valueOf(2))).mod(MOD);
		return a.multiply(POW(a.multiply(a).mod(MOD),n.divide(BigInteger.valueOf(2)))).mod(MOD);
	}
	static class FastScanner{
		BufferedReader br;
		StringTokenizer st;
		public FastScanner(){br=new BufferedReader(new InputStreamReader(System.in));}
		String nextToken(){
			while(st==null||!st.hasMoreElements())
				try{st=new StringTokenizer(br.readLine());}catch(Exception e){}
			return st.nextToken();
		}
		int nextInt(){return Integer.parseInt(nextToken());}
		long nextLong(){return Long.parseLong(nextToken());}
		double nextDouble(){return Double.parseDouble(nextToken());}
	}
}
