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

public class K
{
	public static void main(String[] arg)
	{
		new K();
	}
	public K()
	{
		Scanner in = new Scanner(System.in);
		long A = in.nextLong();
		long B = in.nextLong();
		long n = in.nextLong();
		long x = in.nextLong();
		long[][] mat = new long[3][3];
		long[][] ans = new long[3][1];
		long MOD = 1_000_000_007;
		mat[0][0] = A;
		mat[0][2] = B;
		mat[1][0] = 1;
		mat[2][2] = 1;
		ans[2][0] = 1;
		ans[1][0] = A*x%MOD+B;
		ans[1][0] %= MOD;
		ans[0][0] = ans[1][0]*A%MOD+B;
		ans[0][0] %= MOD;
		long[][] ret = expo(mat, n-1, MOD);
//		for(long[] a : ret) System.out.println(Arrays.toString(a));
//		for(long[] a : ans) System.out.println(Arrays.toString(a));
		long[][] answer = multiply(ret, ans, MOD);
//		for(long[] a : answer) System.out.println(Arrays.toString(a));
//		System.out.println(answer[0][0] + " " + answer[1][0]);
		System.out.println(answer[1][0]);
		in.close();
	}
	public long[][] expo(long[][] a, long n, long mod)
	{
//		if(n.equals(BigInteger.valueOf(1)))
		if(n == 1)
			return a;
//		if(n.equals(BigInteger.valueOf(0)))
		if(n == 0)
			return identity(a);
		long[][] answer = expo(a, n/2, mod);
		answer = multiply(answer, answer, mod);
		if(n%2 == 1)
			answer = multiply(answer, a, mod);
		return answer;
	}
	public long[][] identity(long[][] mat)
	{
		long[][] ret = new long[mat.length][mat[0].length];
		for(int i = 0; i < ret.length; i++)
			ret[i][i] = 1;
		return ret;
	}
	// Multiply 2 matrixes together
	// Semi-tested
	public long[][] multiply(long[][] a, long[][] x, long mod)
	{
		if(a[0].length != x.length)
			return null;
		long[][] answer = new long[a.length][x[0].length];
		for(int i = 0; i < answer.length; i++)
		{
			for(int j = 0; j < answer[i].length; j++)
				answer[i][j] = 0;
		}
		for(int i = 0; i < answer.length; i++)
		{
			for(int j = 0; j < answer[i].length; j++)
			{
				for(int k = 0; k < x.length; k++)
				{
					answer[i][j] += a[i][k]*x[k][j]%mod;
					answer[i][j] %= mod;
				}
			}
		}
		return answer;
	}
}